All submissions for this problem are available.
Problem Statement :
Shreya is currently the top rated programmer of the college. She loves to solve problems which are based on range query.
But this time she wants to check the problem solving skills of her friend Komal. Thus she gives her the following equation :
X + Y = 10^9
She also gives her an array(A) of N distinct integers denoting the X coordinate in the above equation. Now she asks Q queries. In each query she gives a range[L,R] and an integer K and asks to find the X coordinate in the range[L,R] such that the corresponding Y coordinate is closest to K. If there exists more than one such X coordinate then print the smallest among them.
Since Komal is busy in organsing the contest, she asks you for help. Can you solve this problem for her?
NOTE : All indexing are 1 based.
First line contains two space seperated integers N [size of the array(A)] and Q (number of queries to ask).
Second line contains N space separated integers of array(A).
Next Q lines contain three space sepereted integers L , R and K.
For each Q, print a single integer in new line denoting the answer to the query.
1<=N<=10^5 1<=A[i]<=10^9 1<=Q<=10^4 1<=L<=R<=N 1<=K<=10^9
Subtask #1(100 points)
7 4 3 2 4 1 5 12 6 2 6 10 1 4 3 2 5 3 5 6 2
12 4 5 12
Testcase 1 :
For first query in range[2,6] the X coordinate having corresponding Y coordinate closest to K(10) is 12.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions