P9807 [POI 2022/2023 R1] wyp

题目译自 [POI2022~2023R1 wyp](https://sio2.mimuw.edu.pl/c/oi30-1/p/wyp/)。

你在高速上开着你新买的车，高速上共有 $2$ 个车道（分为左右，初始时所有车辆都在右侧），$n$ 辆在前面的车，但是由于这些车开的实在是太慢了，你想要进行超车。 已知你的速度为 $V$，其他车速度为 $v_i$（保证 $V > v_i$），如果你的车的车头已经要撞上其他车了，那么你将会向左开进行超车，如果你当前右侧位置存在一个空隙使得你的车进入的了，那么你一定进行右侧。 注意此处存在其他车相撞的情况，后面的车的速度会改成与它前面一样的速度。 问你的车会进行几次左转操作。

第一行四个整数 $n$，$D$，$W$，$M$（$1 \leq n \leq 10^5$，$ 1 \leq D \leq 10^9$，$1 \leq W,M \leq 1000$），分别表示卡车的数量，自己车的长度，自己车的速度为 $W/M$，默认自己车的车头坐标为 $0$。 接下来 $n$ 行，每行 $4$ 个整数 $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$），分别表示其他车的坐标、长度，速度为 $w_i / m_i$。 保证按 $x_i$ 升序排序给出。

输出要实行超车 $n$ 辆车要左转的次数。

样例解释：  子任务分配如下： | 子任务编号 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $1$ | $v_i = v_{i+1}$ | $10$ | | $2$ | $v_i \leq v_{i+1}$ | $20$ | | $3$ | $n \leq 1000$ | $35$ | | $4$ | 无附加限制 | $35$ | 本题中，子任务 $0$ 为样例。