Corrupt Horse Racing
All submissions for this problem are available.
Students’ Gymkhana, IIT Kanpur has started horse-racing games as a refreshment activity in the campus where the students can take part in horse racing on evenings and weekends. But since everyone is very busy with their academics and upcoming Techkriti, they have decided to outsource the organisational responsibilities of the races to a company.
But unfortunately, the company people are very corrupt. The take bribes from people to place their horses already ahead of the starting line before the start of the race.
As a neutral observer, you are given the task to find out which of the N horses
taking part in the race would be leading at a given time in the contest. The horses are indexed from 0 to N-1.
The first of the input contains T, the number of test cases.
The description of each test case begins on a new line and is as follows:
- two space separated integers N, the number of horses and Q, the number of queries.
- N lines for the horses indexed from 0 to N-1 in order, each containing 2 space separated integers D and S; where, D is the initial distance of the horse from the starting line and S is its speed. All the horses run uniformly at their individual speeds.
- Q lines each containing an integer t, which is the query time.
For each query time t, output a line containing a single integer which is the index of the horse leading at that instant of time. If two horses are leading together at that time, print the index of the horse which will be ahead a split second later.
- T ≤ 5
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 5*105
- 0 ≤ D ≤ 1012
- 1 ≤ S ≤ 105
- 1 ≤ t ≤ 5*105
Input: 1 3 3 0 2 0 1 1 2 5 1 2 Output: 2 2 2
|Time Limit:||0.1 - 0.631075 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions