/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 900 点
問題文
音楽に合わせて数直線上を走り回る、次のようなゲームを考えます。
数直線上に N 個のボタンがあります。i 番目 (1 \leq i \leq N) のボタンは、ゲーム開始 T_i 秒後に座標 X_i に出現します。 また、どのボタンについても出現から D+0.5 秒後に消えます。
プレイヤーは、ゲーム開始時に座標 0 を出発し、N 個すべてのボタンを押すことができればゲームクリアとなります。ボタンは好きな順番で押して構いません。 しかし、本ゲームには特殊ルールがあり、ボタンを押してから次にボタンを押すまでの間に、毎回一度以上座標 0 に移動する必要があります。 それが守られない場合は失格となります。
AtCoder さんは、数直線上を秒速 1 で移動することができます。彼女がゲームクリアする方法は存在しますか。 ただし、ボタンを押すのにかかる時間は無視できるものとします。
\mathrm{TESTCASES} 個のテストケースについて解いてください。
制約
- 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 以下である
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。ここで、\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 行目には、k 番目のテストケースについて、ゲームクリアする方法が存在するならば Yes、存在しないならば 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
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 と出力します。
Score : 900 points
Problem Statement
Consider the following rhythm‑action game on the real line.
There are N buttons. The i‑th button (1 \le i \le N) appears at coordinate X_i exactly T_i seconds after the game starts. Each button disappears D + 0.5 seconds after it appears.
The player starts at coordinate 0 at time 0, and must press all N buttons to win the game. The buttons may be pressed in any order. However, after pressing a button and before pressing another, the player must visit coordinate 0 at least once. Violating this rule results in disqualification.
Ms. AtCoder can move at speed 1 on the line. Can she win the game? Pressing a button takes negligible time.
Solve \mathrm{TESTCASES} test cases.
Constraints
- 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}
- The sum of N over all test cases is at most 100\,000.
- The sum of N^2 over all test cases is at most 2.5 \times 10^7.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_k represents the k-th test case:
\mathrm{TESTCASES}
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_{\mathrm{TESTCASES}}
Each test case is given in the following format:
N D T_1 X_1 T_2 X_2 \vdots T_N X_N
Output
Print \mathrm{TESTCASES} lines. The k-th line should contain Yes if the game is winnable for the k-th test case, and No otherwise.
Sample Input 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
Sample Output 1
Yes No Yes No
For the first test case, the game can be won as follows, so the first line contains Yes.
| Elapsed time | Action / Event |
|---|---|
| 0 seconds | Game starts. |
| 5 seconds | Start moving right from coordinate 0. |
| 25 seconds | Arrive at coordinate 20 and stop. |
| 30 seconds | Button 1 appears at coordinate 20. Press it immediately and head left. |
| 50 seconds | Arrive at coordinate 0. Head right. Button 2 appears at coodinate 10. |
| 60 seconds | Arrive at coordinate 10 and press button 2 (before it disappears at 60.5 seconds). |
For the second test case, the game is unwinnable, so the second line contains No.
For the third test case, the game is winnable, so the third line contains Yes.
For the fourth test case, the game is unwinnable, so the fourth line contains No.