Il Derby della Madonnina
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: data structures, dp, math

The derby between Milan and Inter is happening soon, and you have been chosen as the assistant referee for the match, also known as linesman. Your task is to move along the touch-line, namely the side of the field, always looking very carefully at the match to check for offside positions and other offences.

Football is an extremely serious matter in Italy, and thus it is fundamental that you keep very close track of the ball for as much time as possible. This means that you want to maximise the number of kicks which you monitor closely. You are able to monitor closely a kick if, when it happens, you are in the position along the touch-line with minimum distance from the place where the kick happens.

Fortunately, expert analysts have been able to accurately predict all the kicks which will occur during the game. That is, you have been given two lists of integers, $$$t_1, \ldots, t_n$$$ and $$$a_1, \ldots, a_n$$$, indicating that $$$t_i$$$ seconds after the beginning of the match the ball will be kicked and you can monitor closely such kick if you are at the position $$$a_i$$$ along the touch-line.

At the beginning of the game you start at position $$$0$$$ and the maximum speed at which you can walk along the touch-line is $$$v$$$ units per second (i.e., you can change your position by at most $$$v$$$ each second). What is the maximum number of kicks that you can monitor closely?

Input format:
The first line contains two integers $$$n$$$ and $$$v$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le v \le 10^6$$$) — the number of kicks that will take place and your maximum speed.

The second line contains $$$n$$$ integers $$$t_1, \ldots, t_n$$$ ($$$1 \le t_i \le 10^9$$$) — the times of the kicks in the match. The sequence of times is guaranteed to be strictly increasing, i.e., $$$t_1 < t_2 < \cdots < t_n$$$.

The third line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the positions along the touch-line where you have to be to monitor closely each kick.

Output format:
Print the maximum number of kicks that you can monitor closely.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, it is possible to move to the right at maximum speed for the first $$$3.5$$$ seconds and stay at position $$$7$$$ until the first kick happens, and then immediately move right also at maximum speed to watch the second kick at position $$$17$$$. There is no way to monitor closely the third kick after the second kick, so at most $$$2$$$ kicks can be seen.

Example input:
3 2
5 10 15
7 17 29

Example output:
2

Example input:
5 1
5 7 8 11 13
3 3 -2 -2 4

Example output:
3

Editorial:
Let $$$x_i := v t_i - a_i$$$ and $$$y_i := v t_i + a_i$$$ for $$$i = 1, \, \ldots, \, n$$$. The main observation to solve this problem is that a sequence of kicks with indices $$$i_1, \, \ldots, \, i_k$$$ can be seen (in this order and starting from the first one) if and only if both sequences $$$x_{i_1}, \, \ldots, \, x_{i_k}$$$ and $$$y_{i_1}, \, \ldots, \, y_{i_k}$$$ are nondecreasing. To see this, observe that $$$$$$x_i \leq x_j \iff v t_i - a_i \leq v t_j - a_j \iff a_j - a_i \leq v(t_j - t_i)$$$$$$ and $$$$$$y_i \leq y_j \iff v t_i + a_i \leq v t_j + a_j \iff a_i - a_j \leq v(t_j - t_i).$$$$$$ Moreover $$$$$$t_i = \frac{x_i + y_i}{2 v},$$$$$$ so if both sequences are nondecreasing, then their corresponding times are in increasing order and it holds that $$$|a_{i_{\ell+1}} - a_{i_{\ell}}| \leq v(t_{i_{\ell+1}} - t_{i_{\ell}})$$$, which means that each event can be reached from the previous one. The converse is clear from the previous inequalities.
In order to impose the condition that the events can be reached starting from position $$$0$$$ at time $$$0$$$, it is enough to remove all points which cannot be reached from the origin, that is, with $$$|a_i| > v t_i$$$. We will assume that these events have been eliminated and still denote by $$$n$$$ the total number of events.
We have thus reduced the problem to finding the longest increasing subsequence of the $$$y$$$-values when ordered by increasing $$$x$$$-value. More precisely, let $$$(p_1, \, \ldots, \, p_n)$$$ be the permutation of $$$(1, \, \ldots, \, n)$$$ such that $$$$$$i < j \implies x_{p_i} < x_{p_j} \text{ or } (x_{p_i} = x_{p_j} \text{ and } y_{p_i} < y_{p_j}).$$$$$$ Then the solution of the problem is the length of the longest (non-strictly) increasing subsequence of the list $$$y_{p_1}, \, \ldots, \, y_{p_n}$$$.
There are classical algorithms to solve this efficiently in $$$\mathcal O(n \log n)$$$ time. For instance, this complexity is achieved by an approach that processes the elements from left to right and uses binary searches to update the value of the smallest possible last element of a length-$$$k$$$ increasing subsequence in every prefix for every $$$k$$$.