[POI 2022/2023 R1] wyp

Luogu
IDLGP9807
Time1500ms
Memory256MB
DifficultyP6
POI(波兰)20222023
你在高速上开着你新买的车,高速上共有 $2$ 个车道(分为左右,初始时所有车辆都在右侧),$n$ 辆在前面的车,但是由于这些车开的实在是太慢了,你想要进行超车。 已知你的速度为 $V$,其他车速度为 $v_i$(保证 $V > v_i$),如果你的车的车头已经要撞上其他车了,那么你将会向左开进行超车,如果你当前右侧位置存在一个空隙使得你的车进入的了,那么你一定进行右侧。 注意此处存在其他车相撞的情况,后面的车的速度会改成与它前面一样的速度。 问你的车会进行几次左转操作。 ## Input 第一行四个整数 $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$ 升序排序给出。 ## Output 输出要实行超车 $n$ 辆车要左转的次数。 [samples] ## Background 题目译自 [POI2022~2023R1 wyp](https://sio2.mimuw.edu.pl/c/oi30-1/p/wyp/)。 ## Note 样例解释: ![](https://cdn.luogu.com.cn/upload/image_hosting/ymk60iqd.png) 子任务分配如下: | 子任务编号 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $1$ | $v_i = v_{i+1}$ | $10$ | | $2$ | $v_i \leq v_{i+1}$ | $20$ | | $3$ | $n \leq 1000$ | $35$ | | $4$ | 无附加限制 | $35$ | 本题中,子任务 $0$ 为样例。
Samples
Input #1
3 1 1 1
3 2 1 4
6 3 1 2
10 2 1 4
Output #1
2
API Response (JSON)
{
  "problem": {
    "name": "[POI 2022/2023 R1] wyp",
    "description": {
      "content": "你在高速上开着你新买的车,高速上共有 $2$ 个车道(分为左右,初始时所有车辆都在右侧),$n$ 辆在前面的车,但是由于这些车开的实在是太慢了,你想要进行超车。 已知你的速度为 $V$,其他车速度为 $v_i$(保证 $V > v_i$),如果你的车的车头已经要撞上其他车了,那么你将会向左开进行超车,如果你当前右侧位置存在一个空隙使得你的车进入的了,那么你一定进行右侧。 注意此处存在其他车相撞",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9807"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你在高速上开着你新买的车,高速上共有 $2$ 个车道(分为左右,初始时所有车辆都在右侧),$n$ 辆在前面的车,但是由于这些车开的实在是太慢了,你想要进行超车。\n\n已知你的速度为 $V$,其他车速度为 $v_i$(保证 $V > v_i$),如果你的车的车头已经要撞上其他车了,那么你将会向左开进行超车,如果你当前右侧位置存在一个空隙使得你的车进入的了,那么你一定进行右侧。\n\n注意此处存在其他车相撞...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments