题目详情题解（0）讨论（0）提交记录（0）

AT_abc434_c.[ABC434C] Flapping Takahashi

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Takahashi 决定用气球在天空中飞翔。Takahashi 在时间 00 时刻的高度为 HH（单位为秒），并且将从现在开始飞行 10910^9 秒。

Takahashi 每秒钟最多可以改变 11 的高度。但是，他不能让自己的高度降到 00 或以下。

  • 换句话说，若 F(t)F(t) 表示 Takahashi 在时间 tt 时的高度，则 F(t)F(t) 满足以下所有条件：
    • F(0)=HF(0) = H；
    • −1≤F(u)−F(t)u−t≤1-1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1，其中 0≤t<u≤1090 \leq t < u \leq 10^9；
    • F(t)>0F(t) > 0，其中 0≤t≤1090 \leq t \leq 10^9。

现有 NN 个关于高度的目标，第 ii 个目标要求在时间 tit_i 时他的高度至少为 lil_i，至多为 uiu_i。
询问是否存在一种飞行方式，使 Takahashi 可以满足所有目标。

给出 TT 组测试数据，请分别解答每一组情况。

输入格式

输入从标准输入读入，格式如下，其中 casei\mathrm{case}_i 表示第 ii 组测试数据：

$ 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 $

输出格式

输出 TT 行，第 ii 行是字符串 Yes（如果存在可行方案），否则输出 No，表示第 ii 组测试数据的答案。

输入输出样例

  • 输入#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

对于第一组测试数据，Takahashi 可以按如下方式飞行以满足所有目标：

  • 在时间 00 时，他的高度为 55。
  • 从时间 00 到时间 22，以每秒 0.50.5 的速度下降。
  • 在时间 22 时，高度为 5−0.5×2=45 - 0.5 \times 2 = 4。
  • 从时间 22 到时间 33，保持高度不变。
  • 在时间 33 时，高度为 44，满足第一个目标。
  • 从时间 33 到时间 88，以每秒 11 的速度上升。
  • 在时间 88 时，高度为 4+1×5=94 + 1 \times 5 = 9，满足第二个目标。

对于第二组测试数据，无论怎样飞行都无法满足所有目标。

数据范围

  • 1≤T≤1051 \leq T \leq 10^5
  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤H≤1091 \leq H \leq 10^9
  • 1≤t1<t2<⋯<tN≤1091 \leq t_1 < t_2 < \dots < t_N \leq 10^9
  • 1≤li≤ui≤1091 \leq l_i \leq u_i \leq 10^9
  • 所有测试数据中 NN 的总和不超过 10510^5。
  • 所有输入数均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页