Flapping Takahashi

AtCoder

IDabc434_c

Time2000ms

Memory256MB

Difficulty—

Takahashi has decided to fly in the sky with balloons. Takahashi is at altitude $H$ at time $0$ (the unit is seconds), and will fly for $10^9$ seconds from now. Takahashi can change his flying altitude by up to $1$ per second. However, he cannot make his altitude $0$ or less. * In other words, if $F(t)$ denotes Takahashi's altitude at time $t$, then $F(t)$ satisfies all of the following conditions: * $F(0) = H$ * $-1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1$ for $0 \leq t \lt u \leq 10^9$. * $F(t) \gt 0$ for $0 \leq t \leq 10^9$. There are $N$ goals regarding altitude. The $i$\-th goal is to make the altitude at time $t_i$ at least $l_i$ and at most $u_i$. Is it possible for Takahashi to fly in a way that achieves all goals? You are given $T$ test cases; solve each of them. ## Constraints * $1 \leq T \leq 10^5$ * $1 \leq N \leq 10^5$ * $1 \leq H \leq 10^9$ * $1 \leq t_1 \lt t_2 \lt \dots \lt t_N \leq 10^9$ * $1 \leq l_i \leq u_i \leq 10^9$ * The sum of $N$ over all test cases is at most $10^5$. * All input values are integers. ## Input The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$\-th test case. $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ Each test case is given in the following format: $N$ $H$ $t_1$ $l_1$ $u_1$ $t_2$ $l_2$ $u_2$ $\vdots$ $t_N$ $l_N$ $u_N$ [samples]

Samples

Input #1

Output #1

Yes
No
Yes

For the first test case, Takahashi can achieve all goals by flying as follows:

*   At time $0$, he is at altitude $5$.
*   From time $0$ to time $2$, he descends at a rate of $0.5$ per second.
*   At time $2$, he is at altitude $5 - 0.5 \times 2 = 4$.
*   From time $2$ to time $3$, he stays at the same altitude.
*   At time $3$, he is at altitude $4$. He satisfies the first goal.
*   From time $3$ to time $8$, he ascends at a rate of $1$ per second.
*   At time $8$, he is at altitude $4 + 1 \times 5 = 9$. He satisfies the second goal.

For the second test case, he cannot achieve all goals no matter how he flies.

API Response (JSON)

{
  "problem": {
    "name": "Flapping Takahashi",
    "description": {
      "content": "Takahashi has decided to fly in the sky with balloons. Takahashi is at altitude $H$ at time $0$ (the unit is seconds), and will fly for $10^9$ seconds from now. Takahashi can change his flying altitud",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc434_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi has decided to fly in the sky with balloons. Takahashi is at altitude $H$ at time $0$ (the unit is seconds), and will fly for $10^9$ seconds from now.\nTakahashi can change his flying altitud...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments