← 返回题目列表

AtCoder · agc072_a

A. 节奏游戏

中文机器翻译题面 查看原题

分数: 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.