You are not logged in. Please login at www.codechef.com to post your questions!

×

MQRY Editorial

Problem Link : Contest Practice

Author and Editorialist : Arun Prasad

DIFFICULTY:

EASY

PREREQUISITES:

Segment Trees

PROBLEM:

Given the range of indexes print the difference between the largest and smallest value in the given range

EXPLANATION:

Create a segment tree for the given array, for each node in the segment tree maintain two variable, one for the smallest value in the sements range and other one for largest value in the segments range.

Author's Solution :

Link For Authors Solution

asked 29 Jun '15, 19:02

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

edited 29 Jun '15, 19:09


Sir,I think the cases set were weak.

I solved the problem by both the methods-Segment Tree and the naive algorithm(checking over and over again by iterating between the bounds of the query).

Segment Tree method was pretty fast - 0.05s Segment tree solution

But Naive algorithm also worked - 0.62s Naive Solution

Another method worked at 0.24s link

Can you tell me the cases set by you for testing the solution so that I can understand the Time taken.

Thank You.

link

answered 30 Jun '15, 01:18

prrateekk's gravatar image

3★prrateekk
534216
accept rate: 12%

edited 30 Jun '15, 01:20

Thanks For letting me know about this issue.I will try to change the Test Cases .

(30 Jun '15, 11:52) geek_geek4★

Test Cases Updated ! Navie method wont work and will give TLE

(01 Jul '15, 22:49) geek_geek4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,482
×3,706
×1,726
×6
×2

question asked: 29 Jun '15, 19:02

question was seen: 2,297 times

last updated: 01 Jul '15, 22:49