Codeforces Round #745 (Div. 2) Train Maintenance Solution (Java/C++)

Solution:

First of all, we can almost immediately notice that if x[i]>m, then this must have no effect, and we can ignore it directly. Therefore, the value range of x[i] is reduced from 0~$10^9$ to 0~$2\cdot 10^5$.

Further if x[i]<$2\cdot 10^5$ and x[i]+y[i]>m. For this situation, it is very clear, after the addition of i is added, and then after x[i], the answer is permanently increased by 1 (unless it is removed).
Therefore, it is natural to think that, similar to the parenthesis matching problem, mark +1 at now+x[i], mark -1 at now+x[i]+y[i], and use a sum variable to record the sum of +1/-1 marks for current time.

In fact, the above approach has been able to cover the relatively large x[i]+y[i] situation, because if x[i]+y[i] is relatively large, we only need to repeat the mark $\frac m {x[i]+y[i]}$ times.
But if x[i]+y[i] is very small (such as 2), you need to mark $\frac m 2$ times. So it is the time complexity of $m^2$.

For the case where x[i]+y[i] is very small, taking 2 as an example, in fact, it only depends on the time when i is added. Similarly, when x[i]=1 and y[i]=2, we only need to know whether the current time i is under maintenance according to the value of (now-add time)%3.

Therefore, we use $\sqrt m \approx 450$ as the boundary. If it is greater than 450, it is done by pairing the brackets, and if it is less than 450, it can be done by taking the remainder.

Code:

Java

C++