分数: 300 点
问题陈述
高桥决定带着气球在天上飞。高桥 位于海拔 H 时间 0 (单位为秒),将飞行 10^9 秒后。
高桥最多可以改变他的飞行高度 1 每秒。然而他无法让自己的高度 0 或更少。
- 换句话说,如果 F(t) 表示高桥当时的海拔高度 t,那么 F(t) 满足以下所有条件:
- F(0) = H
- -1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1 为 0 \leq t \lt u \leq 10^9.
- F(t) \gt 0 为 0 \leq t \leq 10^9.
有 N 有关海拔的目标。的 i-th 目标是使高度在某个时间 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- 第行应包含 Yes 如果可以以实现所有目标的方式飞行 i- 第一个测试用例,以及 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
对于第一个测试用例,高桥可以通过飞行实现所有目标,如下:
- 时间 0,他处于海拔高度 5.
- 从时间 0 到时间 2,他以以下速率下降 0.5 每秒。
- 时间 2,他处于海拔高度 5 - 0.5 \times 2 = 4.
- 从时间 2 到时间 3,他保持在相同的高度。
- 时间 3,他处于海拔高度 4。他实现了第一个目标。
- 从时间 3 到时间 8,他以以下速度上升 1 每秒。
- 时间 8,他处于海拔高度 4 + 1 \times 5 = 9。他实现了第二个目标。
对于第二个测试用例,无论他如何飞翔都无法实现所有目标。