MQRY Editorial

editorial
, , , ,
1

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

2

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.

2 Likes
3

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

4

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