P9807 [POI 2022/2023 R1] wyp

This problem is translated from [POI2022~2023R1 wyp](https://sio2.mimuw.edu.pl/c/oi30-1/p/wyp/)。

You are driving your newly bought car on a highway. The highway has $2$ lanes (left and right). Initially, all vehicles are in the right lane. There are $n$ cars in front of you, but they are too slow, so you want to overtake them. Your speed is $V$, and the speed of the $i$-th other car is $v_i$ (it is guaranteed that $V > v_i$). If the front of your car is about to crash into another car, you will steer left to overtake. If, at your current position, there is a gap on the right lane that allows your car to move into it, then you will definitely move to the right. Note that collisions between other cars may happen. After a collision, the speed of the car behind will change to be the same as the speed of the car in front of it. Determine how many times your car will make a left-turn operation.

The first line contains four integers $n$, $D$, $W$, $M$ ($1 \leq n \leq 10^5$, $1 \leq D \leq 10^9$, $1 \leq W,M \leq 1000$), representing the number of trucks, the length of your car, your car’s speed $W/M$, and it is assumed that the coordinate of the front of your car is $0$. The next $n$ lines each contain four integers $x_i$, $d_i$, $w_i$, $m_i$ ($1 \leq x_i,d_i \leq 10^9$, $1 \leq w_i,m_i \leq 1000$), representing the position, length, and speed $w_i / m_i$ of the other cars. It is guaranteed that the input is given in increasing order of $x_i$.

Output the number of left turns needed to overtake $n$ cars.

Explanation of the sample:  The subtasks are as follows: | Subtask ID | Special Property | Score | | :----------: | :----------: | :----------: | | $1$ | $v_i = v_{i+1}$ | $10$ | | $2$ | $v_i \leq v_{i+1}$ | $20$ | | $3$ | $n \leq 1000$ | $35$ | | $4$ | No additional constraints | $35$ | In this problem, subtask $0$ is the sample. Translated by ChatGPT 5