Problem Statement
You are given two lists of integers, T and A, where:
t[i] represents the launch time of the i-th missile.a[i] represents the position where you need to be to watch the i-th missile launch.
Starting at position 0, you can move up to X units per second. Your objective is to maximize the number of launches you can watch. You can watch a launch if you are at the required position a[i] exactly at the time t[i].
Input Format
The first line contains two integers N and X—the number of missile launches and your maximum speed.
The second line contains N integers t1, t2, ..., tn — the times of the launches in the mission in increasing order.
The third line contains N integers a1, a2, ..., an — the positions along the boundary where you need to be to watch each launch closely.
Output Format
Print the maximum number of launches that you can watch closely.
Constraints
1<=N<=2*1e5
1<=X<=1e6
1<=t[i]<=1e9
-1e9<=a[i]<=1e9
Sample Testcase 1
Input
1 2
3
7
Output
0
Explanation
He cannot reach any missile launch positions on time, so he can't watch any missile attacks.
Sample Testcase 2
Input
3 2
5 10 15
7 17 29
Output
2
Explanation
- Initial Position: Start at position
0. - At time 5: Go to
7 with speed 2 for 3.5 seconds to reach there just in time to watch the missile launch. - At time 10: Immediately move to
17 from 7, traveling at your maximum speed of 2 units per second, arriving precisely as the second launch occurs. - Therefore, the maximum number of launches you can monitor closely is
2.
Full text and comments »
