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 翻译