Rhythm Game

AtCoder

IDagc072_a

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

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

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`.

API Response (JSON)

{
  "problem": {
    "name": "Rhythm Game",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc072_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider the following rhythm‑action game on the real line.\n\n> 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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments