题目描述
在一条无穷长的数轴上摆放着 n 个箱子。第 i (1≤i≤n) 个箱子在时刻 0 位于数轴 ai 处,而你希望在时刻 ti 以及之后的所有时刻,这个箱子处在数轴的 bi 处。保证序列 [a1,…,an] 和 [b1,…,bn] 单调递增。
为此,从时刻 0 开始的每个单位时间里,你可以将某个箱子在数轴上移动一个单位长度,也可以什么都不做。你需要保证任意时刻每个点上都只有一个箱子。形式化地,每个单位时间里你可以按照以下方式进行一次操作,也可以不进行操作:
- 选择任意一个箱子。记其编号为 i,它目前的位置为 pi。
- 选择一个方向 d∈{±1},其中 d=1 代表向右,d=−1 代表向左。你需要保证数轴上 (pi+d) 处没有箱子。
- 将 i 号箱子从点 pi 移动到点 (pi+d) 处。
你想知道,是否存在一种操作方法同时满足所有箱子的要求,即对于任意 1≤i≤n,第 i 个箱子在时刻 ti 以及之后的所有时刻都处于数轴的 bi 处。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T,分别表示测试点编号和测试数据组数,接下来输入每组测试数据。样例满足 c=0。
对于每组测试数据,第一行一个整数 n,表示箱子的个数,接下来 n 行,第 i (1≤i≤n) 行三个整数 ai,bi,ti,分别表示第 i 个箱子的初始位置、目标位置和时刻要求。
输出格式
对于每组测试数据,输出一行一个字符串 Yes
或 No
,表示是否存在一种操作方法同时满足所有箱子的要求。
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.in
与 move/move2.ans
。
该组样例共有 6 组测试数据,所有数据均满足特殊性质 A。其中每组测试数据的 n 分别为 7、7、7、200、3000、2×105,且测试数据 1∼3 满足 ai,bi≤15,测试数据 4 满足 ai,bi≤3,000。
【样例 3】
见选手目录下的 move/move3.in
与 move/move3.ans
。
该组样例共有 6 组测试数据,所有数据均满足特殊性质 B。其中每组测试数据的 n 分别为 7、7、7、200、3000、2×105,且测试数据 1∼3 满足 ai,bi≤15,测试数据 4 满足 ai,bi≤3,000。
【样例 4】
见选手目录下的 move/move4.in
与 move/move4.ans
。
该组样例共有 6 组测试数据,所有数据均满足特殊性质 C。其中每组测试数据的 n 分别为 7、7、7、200、3000、2×105,且测试数据 1∼3 满足 ai,bi≤15,测试数据 4 满足 ai,bi≤3,000。
【样例 5】
见选手目录下的 move/move5.in
与 move/move5.ans
。
该组样例共有 6 组测试数据。其中每组测试数据的 n 分别为 7、7、7、200、3000、2×105,且测试数据 1∼3 满足 ai,bi≤15,测试数据 4 满足 ai,bi≤3,000。
【子任务】
对于所有测试点,
- 1≤T≤6,
- 1≤n≤2×105,
- $\forall 1 \leq i \leq n, 1 \leq a_i, b_i \leq 10^9, 0 \leq t_i \leq 10^{16}$,
- ∀1≤i<n,ai<ai+1,bi<bi+1。
测试点编号 |
n≤ |
ai,bi≤ |
特殊性质 |
1 |
7 |
15 |
A |
2,3 |
无 |
4 |
200 |
3000 |
A |
5 |
B |
6,7 |
无 |
8 |
3000 |
109 |
A |
9 |
B |
10,11 |
无 |
12 |
8×104 |
5×105 |
A |
13 |
B |
14,15 |
C |
16∼18 |
无 |
19,20 |
2×105 |
109 |
B |
21,22 |
C |
23∼25 |
无 |
- 特殊性质 A:∀1≤i<j≤n,ti=tj。
- 特殊性质 B:∀1≤i≤n,ai≤bi 且 ∀1≤i<n,bi<ai+1。
- 特殊性质 C:∀1≤i≤n,ai≤bi。