← 返回题目列表

AtCoder · abc434_c

F. 扑腾的高桥

中文机器翻译题面 查看原题

分数: 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。他实现了第二个目标。

对于第二个测试用例,无论他如何飞翔都无法实现所有目标。