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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, 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

?