×

# IIITBH - Editorial

Contest

Author: Subash Chandra Manohari

Tester: D Teja Vardhan Reddy

Editorialist: Subash Chandra Manohari

EASY-MEDIUM

Segment tree

# PROBLEM:

The problem is to find the difference between the IDs of the students having same score in a given range $[L,R]$.

# EXPLANATION:

For this interval type of queries, we can think of solving it using segment trees.

We can make a node which can store the minimum and maximum indices of a given mark. If the range represented by a node is completely within the given range, return the node which has the minimum and maximum indices of marks in the range. And if the range represented by a node is partially inside and partially outside the given range, return node of the left child and the right child.

Using this, both Update and Query operation can be done in $O(Log n)$ time and the building of tree will take $O(n)$ time. So the overall time complexity of the solution will be $O(n Log n)$

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here. (Alternate solution)

This question is marked "community wiki".

4★subash1
11
accept rate: 0%

19.8k350498541

 0 Alternate solution without using segment tree. Used sets to store id of students having a particular score. https://www.codechef.com/viewsolution/22915966 answered 07 Feb, 20:50 3●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,678
×1,755
×160