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