/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は風船で空を飛ぶことにしました。高橋君は時刻 0 (単位は秒) の時点で高度 H にいて、これから 10^9 秒間飛行します。
高橋君は自身が飛んでいる高度を 1 秒あたり 1 まで変化させることが出来ます。ただし、高度を 0 以下にすることはできません。
- 言い換えると、高橋君の時刻 t における高度を F(t) とした時、F(t) は以下の条件を全て満たします。
- F(0) = H
- 0 \leq t \lt u \leq 10^9 において -1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1
- 0 \leq t \leq 10^9 において F(t) \gt 0
N 個の高度に関する目標があります。i 個目の目標は時刻 t_i 時点での高度を l_i 以上 u_i 以下にすることです。
高橋君は目標を全て達成するような飛行が可能ですか？
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。
制約
- 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
- 全てのテストケースにおける N の総和は 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N H t_1 l_1 u_1 t_2 l_2 u_2 \vdots t_N l_N u_N
出力
T 行出力せよ。i 行目には、i 番目のテストケースにおいて目標を全て達成するような飛行が可能である場合 Yes を、そうでない場合 No を出力せよ。
入力例 1
3 2 5 3 1 4 8 9 11 2 6 1 1 4 3 5 8 10 36 27 37 38 30 34 54 38 20 77 45 1 36 49 38 51 52 31 58 65 43 60 71 14 42 73 36 38 85 14 29
出力例 1
Yes No Yes
1 番目のテストケースについて、高橋君は以下の方法で飛行することで全ての目標を達成することが出来ます。
- 時刻 0 の時点で高橋君は高度 5 にいる。
- 時刻 0 から時刻 2 にかけて高橋君は秒速 0.5 で高度を下げる。
- 時刻 2 の時点で高橋君は高度 5 - 0.5 \times 2 = 4 にいる。
- 時刻 2 から時刻 3 の間、高橋君は同じ高度にとどまる。
- 時刻 3 の時点で高橋君は高度 4 にいる。高橋君は 1 番目の目標を満たす。
- 時刻 3 から時刻 8 にかけて高橋君は秒速 1 で高度を上げる。
- 時刻 8 の時点で高橋君は高度 4 + 1 \times 5 = 9 にいる。高橋君は 2 番目の目標を満たす。
2 番目のテストケースについて、高橋君はどのように飛行しても目標を全て達成することは出来ません。
Score : 300 points
Problem Statement
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
Output
Output T lines. The i-th line should contain Yes if it is possible to fly in a way that achieves all goals in the i-th test case, and No otherwise.
Sample Input 1
3 2 5 3 1 4 8 9 11 2 6 1 1 4 3 5 8 10 36 27 37 38 30 34 54 38 20 77 45 1 36 49 38 51 52 31 58 65 43 60 71 14 42 73 36 38 85 14 29
Sample 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.