All Tracks Algorithms Searching Binary Search Problem

Little Monk and Mountains
Tag(s):

Algorithms, Binary Search, Easy-Medium

Problem
Editorial
Analytics

Little monk has travelled across the world but he has never seen a place like byteland. The mountains in the byteland have a unique order. Height of $$i^{th}$$ mountain is represented by an interval $$(l_i,\;r_i)$$ i.e. the height of the mountain is in increasing order, $$l_i, l_i+1, l_i+2, ...., r_i$$. The heights of mountains are such that if $$i < j$$ then $$r_i < l_j$$. Now the little monk wants to know $$x^{th}$$ smallest height in the byteland.

Note: x will be always in the given range of intervals.

Input Format:
First line contains two space separated integers, $$N$$ $$(1 \le N \le 10^5)$$ and $$Q$$ $$(1 \le Q \le 10^5)$$, number of mountains and number of queries.
Next $$N$$ lines contains two separated integers each, $$l_i$$ and $$r_i$$ $$(1 \le l_i, r_i \le 10^{18})$$. $$i^{th}$$ line contains the starting height and the end height of the $$i^{th}$$ mountain.
Next $$Q$$ lines contains one integer, $$x$$ $$(1 \le x \le 10^{18})$$, each, denoting the queries.

Output Format:
For each query, print $$x^{th}$$ smallest height in the byteland.

SAMPLE INPUT
3 3
1 10
11 20
21 30
5
15
25
SAMPLE OUTPUT
5
15
25
Explanation

enter image description here

The mountains will look like the image above. So the heights will be $$[1, 2, 3, 4, ....., 8, 9, 10, 11, 12, 13, ...., 19, 20, 21, 22, ......, 29, 30]$$.

$$5^{th}$$ smallest height will be $$5$$.
$$15^{th}$$ smallest height will be $$15$$.
$$25^{th}$$ smallest height will be $$25$$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Searching)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications