All submissions for this problem are available.
It's time for the annual exciting Motorbike Race in Byteland.
There are N motorcyclists taking part in the competition. Johnny is watching the race. At the present moment (time 0), Johnny has taken note of the current velocity and position of each motorcyclist.
Johnny wants to know at a given point of time, which motorcyclist is in a specific place in the rank list. Please help him!
If at any given time two motorcyclists are in same position, the motorcyclist with the smaller index will be placed before the one with the larger index.
To make the problem simple, Johnny assumes that each motorcyclist is moving at a constant velocity.
The first line contains a number t (about 10) which is the number of test cases. Then t test cases follow. Each test case has the following form.
The first line of the test case contains a number N (1 <= N <= 2000), the number of motorcyclists.
The i-th line in the next N lines contains two numbers, v and x, which are the velocity and the current position of the i-th motorcyclist (1 <= v, x <= 100,000).
The next line contains a number Q (1 <= Q <= 2000), the number of time queries.
Each line in the next Q lines contains two numbers, t (1 <= t <= 1,000,000,000) and k (1 <= k <= n), representing the query: "at time t, which motorcyclist is positioned k-th in the rank list?"
For each test case, print Q lines, with each line containing the index of the motorcyclist for the corresponding query.
Remember to print a new line after each test case.
Input: 1 4 2 100 3 50 4 60 5 1 4 1 1 50 2 60 4 100 1 Output: 1 4 1 4
|Time Limit:||0.278448 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, kotlin, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.