Horse Racing
Program time limit: 1 second
Program memory limit: 512 MB
James went to watch horse racing. However, James was lost in anxiety thinking about his future and as such didn't pay attention to the horse racing. James really likes to watch horse racing, but now not only is he anxious, he is also sad that he didn't attend to the race. As such he comes to you to ask which horse is in the lead at at various points in time.
The bad news is that you were not paying attention either! But you know that the competition is actually rigged, each horse starts at a distinct postion and travels at a constant velocity. Thus the results are already predetermined! You hacked into the secret data base and obtained that infromation!
More formally, given $n$ horses, each starting at the position $c_i$ and travelling at a constant velocity of $v_i$, determine which horse is in the lead at time $t_i$. Note that the race starts at $t = 0$
A horse is in the lead if they are at a position greater than all other horses. If a tie breaker with two horses at the same position, the horse previously in the lead is still in the lead.
James will ask you $m$ questions asking which horse is in the lead at a particular time $t_i$.
Input
The first line will contain two space seperated integers $n$ and $m$, indicating that there are $n$ horses, and $m$ queries.
The second line will have $n$ space seperated distinct integers, denoting the initial position of the horses.
The third line will have $n$ space seperated integers, denoting the velocity of the horses.
The fourth line will have $m$ space seperated integers, denoting the time where you have report the leading horse.
Constraints
For all test cases:
- $1 \le n, m \le 100\;000$.
- $1 \le p_i, v_i, t_i \le 1\;000\;000\;000$.
Output
$m$ integers spaced seperated, each integer representing the horse that was in the lead at that time stamp.
Sample Input 1
3 3
1 10 15
10 2 1
1 2 10
Sample Output 1
3 1 1
Explanation 1
Horse 3 starts at the front and is still in the front at time 1, after which horse 1 catches up and takes the lead for the rest of the race.
Scoring
Your program will be run on the 1 sample case and multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves the task. Recall that your final score on the task is the score of your highest scoring submission.
Submit
Log in to submit!Past submissions
You haven't submitted to this task.