#P11833. [省选联考 2025] 推箱子

    ID: 13205 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>线段树二分各省省选2025颜色段均摊(珂朵莉树 ODT)

[省选联考 2025] 推箱子

题目描述

在一条无穷长的数轴上摆放着 nn 个箱子。第 ii (1in1 \leq i \leq n) 个箱子在时刻 0 位于数轴 aia_i 处,而你希望在时刻 tit_i 以及之后的所有时刻,这个箱子处在数轴的 bib_i 处。保证序列 [a1,,an][a_1, \ldots, a_n][b1,,bn][b_1, \ldots, b_n] 单调递增

为此,从时刻 00 开始的每个单位时间里,你可以将某个箱子在数轴上移动一个单位长度,也可以什么都不做。你需要保证任意时刻每个点上都只有一个箱子。形式化地,每个单位时间里你可以按照以下方式进行一次操作,也可以不进行操作:

  1. 选择任意一个箱子。记其编号为 ii,它目前的位置为 pip_i
  2. 选择一个方向 d{±1}d \in \{\pm1\},其中 d=1d = 1 代表向右,d=1d = -1 代表向左。你需要保证数轴上 (pi+d)(p_i + d) 处没有箱子。
  3. ii 号箱子从点 pip_i 移动到点 (pi+d)(p_i + d) 处。

你想知道,是否存在一种操作方法同时满足所有箱子的要求,即对于任意 1in1 \leq i \leq n,第 ii 个箱子在时刻 tit_i 以及之后的所有时刻都处于数轴的 bib_i 处。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc, T,分别表示测试点编号和测试数据组数,接下来输入每组测试数据。样例满足 c=0c = 0

对于每组测试数据,第一行一个整数 nn,表示箱子的个数,接下来 nn 行,第 ii (1in1 \leq i \leq n) 行三个整数 ai,bi,tia_i, b_i, t_i,分别表示第 ii 个箱子的初始位置、目标位置和时刻要求。

输出格式

对于每组测试数据,输出一行一个字符串 YesNo,表示是否存在一种操作方法同时满足所有箱子的要求。

0 2
2
4 5 1
6 7 1
3
4 5 3
7 6 1
10 8 4
No
Yes

提示

【样例 1 解释】

该组样例共有 2 组测试数据。

  • 对于第一组测试数据,答案是否定的。将 1 号箱子由点 4 移动到点 5,并将 2 号箱子由点 6 移动到点 7,至少需要两个单位时间,因此不可能在时刻 1 同时满足两个箱子的条件。
  • 对于第二组测试数据,答案是肯定的,例如如下方法同时满足了所有箱子的要求:
    • 在时刻 0 至时刻 1 的一个单位时间,将 2 号箱子由点 7 移动到点 6;
    • 在时刻 1 至时刻 2 的一个单位时间,将 3 号箱子由点 10 移动到点 9;
    • 在时刻 2 至时刻 3 的一个单位时间,将 1 号箱子由点 4 移动到点 5;
    • 在时刻 3 至时刻 4 的一个单位时间,将 3 号箱子由点 9 移动到点 8;
    • 在之后的所有单位时间,什么都不做。

【样例 2】

见选手目录下的 move/move2.inmove/move2.ans

该组样例共有 66 组测试数据,所有数据均满足特殊性质 A。其中每组测试数据的 nn 分别为 77777720020030003\,0002×1052 \times 10^5,且测试数据 131 \sim 3 满足 ai,bi15a_i, b_i \leq 15,测试数据 44 满足 ai,bi3,000a_i, b_i \leq 3,000

【样例 3】

见选手目录下的 move/move3.inmove/move3.ans

该组样例共有 66 组测试数据,所有数据均满足特殊性质 B。其中每组测试数据的 nn 分别为 77777720020030003\,0002×1052 \times 10^5,且测试数据 131 \sim 3 满足 ai,bi15a_i, b_i \leq 15,测试数据 44 满足 ai,bi3,000a_i, b_i \leq 3,000

【样例 4】

见选手目录下的 move/move4.inmove/move4.ans

该组样例共有 66 组测试数据,所有数据均满足特殊性质 C。其中每组测试数据的 nn 分别为 77777720020030003\,0002×1052 \times 10^5,且测试数据 131 \sim 3 满足 ai,bi15a_i, b_i \leq 15,测试数据 44 满足 ai,bi3,000a_i, b_i \leq 3,000

【样例 5】

见选手目录下的 move/move5.inmove/move5.ans

该组样例共有 66 组测试数据。其中每组测试数据的 nn 分别为 77777720020030003\,0002×1052 \times 10^5,且测试数据 131 \sim 3 满足 ai,bi15a_i, b_i \leq 15,测试数据 44 满足 ai,bi3,000a_i, b_i \leq 3,000

【子任务】

对于所有测试点,

  • 1T61 \leq T \leq 6,
  • 1n2×1051 \leq n \leq 2 \times 10^5,
  • $\forall 1 \leq i \leq n, 1 \leq a_i, b_i \leq 10^9, 0 \leq t_i \leq 10^{16}$,
  • 1i<n,ai<ai+1,bi<bi+1\forall 1 \leq i < n, a_i < a_{i+1}, b_i < b_{i+1}
测试点编号 nn \leq ai,bia_i, b_i \leq 特殊性质
11 77 1515 A
2,32, 3
44 200200 30003\,000 A
55 B
6,76, 7
88 30003\,000 10910^9 A
99 B
10,1110, 11
1212 8×1048 \times 10^4 5×1055 \times 10^5 A
1313 B
14,1514, 15 C
161816 \sim 18
19,2019, 20 2×1052 \times 10^5 10910^9 B
21,2221, 22 C
232523 \sim 25
  • 特殊性质 A:1i<jn,ti=tj\forall 1 \leq i < j \leq n, t_i = t_j
  • 特殊性质 B:1in,aibi\forall 1 \leq i \leq n, a_i \leq b_i1i<n,bi<ai+1\forall 1 \leq i < n, b_i < a_{i+1}
  • 特殊性质 C:1in,aibi\forall 1 \leq i \leq n, a_i \leq b_i