分数: 900 点
问题陈述
考虑以下实线上的节奏动作游戏。
有 N 按钮。的 i第一个按钮 (1 \le i \le N) 出现在坐标处 游戏开始后 X_i 正是 T_i 秒。每个按钮消失 出现后 D + 0.5 秒。
玩家从坐标开始 0 时间 0,并且必须按全部 N 按钮赢得游戏。可以按任何顺序按下按钮。 然而, 在按下一个按钮之后和按下另一个按钮之前,玩家必须访问坐标 0 至少一次。 违反此规则将导致取消资格。
AtCoder女士可以快速移动 1 上线了。她能赢得比赛吗?按下按钮所花费的时间可以忽略不计。
解决 \mathrm{TESTCASES} 测试用例。
约束
- 1 \le \mathrm{TESTCASES} \le 100\,000
- 1 \le N \le 5\,000
- 0 \le D \le 10^{12}
- 0 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12}
- 1 \le X_i \le 10^{12}
- 总和 N 所有测试用例最多 100\,000.
- 总和 N^2 所有测试用例最多 2.5 \times 10^7.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{case}_k 代表 k-第一个测试用例:
\mathrm{TESTCASES}
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_{\mathrm{TESTCASES}}
每个测试用例均按以下格式给出:
N D T_1 X_1 T_2 X_2 \vdots T_N X_N
输出
打印 \mathrm{TESTCASES} 行。的 k- 第行应包含 Yes 如果比赛可以获胜 k- 第一个测试用例,以及 No 否则。
示例输入 1
4 2 10 30 20 50 10 2 9 30 20 50 10 4 185 0 40 0 30 0 20 0 10 5 1312372641 141421356 314159265 237309504 358979323 880168872 846264338 4209698078 327950288 5696718753 419716939
示例输出 1
Yes No Yes No
对于第一个测试用例,游戏可以如下获胜,因此第一行包含 Yes.
| 已用时间 | 动作/事件 |
|---|---|
| 0 秒 | 游戏开始。 |
| 5 秒 | 从坐标开始向右移动 0. |
| 25 秒 | 到达坐标 20 然后停止。 |
| 30 秒 | 按钮 1 出现在坐标处 20。立即按下它并向左走。 |
| 50 秒 | 到达坐标 0。向右走。按钮 2 出现在坐标处 10. |
| 60 秒 | 到达坐标 10 并按下按钮 2 (在它消失之前 60.5 秒)。 |
对于第二个测试用例,游戏无法获胜,因此第二行包含 No.
对于第三个测试用例,游戏是可以获胜的,因此第三行包含 Yes.
对于第四个测试用例,游戏是无法获胜的,因此第四行包含 No.