AT_agc072_a [AGC072A] Rhythm Game

我们来考虑一个在数轴上随着音乐奔跑的游戏，如下所述。 > 数轴上有 $N$ 个按钮。第 $i$ 个按钮（$1 \leq i \leq N$）会在游戏开始后 $T_i$ 秒出现在坐标 $X_i$。此外，每个按钮都会在出现后的 $D+0.5$ 秒后消失。 > > 玩家在游戏开始时从坐标 $0$ 出发，如果能够按下所有 $N$ 个按钮，则游戏通关。按钮可以按任意顺序按下。然而，本游戏有一个特殊规则：每次按下一个按钮后，在按下下一个按钮之前，必须至少回到一次坐标 $0$。如果不遵守这一规则，则判为失格。 AtCoder 可以以每秒 $1$ 的速度在数轴上移动。请判断她是否存在通关的方法。按下按钮所需的时间可以忽略不计。 请你解答 $\mathrm{TESTCASES}$ 个测试用例。

输入通过标准输入给出，格式如下，其中 $\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$ $\cdots$ $T_N$ $X_N$

请输出 $\mathrm{TESTCASES}$ 行。对于第 $k$ 个测试用例，如果存在通关方法则输出 `Yes`，否则输出 `No`。

### 限制条件 - $1 \leq \mathrm{TESTCASES} \leq 100\,000$ - $1 \leq N \leq 5\,000$ - $0 \leq D \leq 10^{12}$ - $0 \leq T_1 \leq T_2 \leq \dots \leq T_N \leq 10^{12}$ - $1 \leq X_i \leq 10^{12}$ - 所有测试用例中 $N$ 的总和不超过 $100\,000$ - 所有测试用例中 $N^2$ 的总和不超过 $2.5 \times 10^7$ - 所有输入的数值均为整数 ### 样例解释 1 对于第 1 个测试用例，可以按如下方式行动，从而通关，因此第 1 行输出 `Yes`。 | 从游戏开始的时间 | 行动・事件说明 | |:---|:---| | $0$ 秒 | 游戏开始。 | | $5$ 秒 | 从坐标 $0$ 向右移动。 | | $25$ 秒 | 到达坐标 $20$ 并停下。 | | $30$ 秒 | 第 1 个按钮在坐标 $20$ 出现，立即按下该按钮，并开始向左移动。 | | $50$ 秒 | 回到坐标 $0$，改变移动方向。此时第 2 个按钮刚好在坐标 $10$ 出现。 | | $60$ 秒 | 到达坐标 $10$，按下第 2 个按钮。该按钮会在游戏开始 $60.5$ 秒后消失，因此来得及。 | 对于第 2 个测试用例，不存在通关方法，因此第 2 行输出 `No`。 对于第 3 个测试用例，存在通关方法，因此第 3 行输出 `Yes`。 对于第 4 个测试用例，不存在通关方法，因此第 4 行输出 `No`。 由 ChatGPT 4.1 翻译