【统一省选2025】推箱子 - 题目

在一条无穷长的数轴上摆放着 $n$ 个箱子。第 $i$ ( $1 \leq i \leq n$ ) 个箱子在时刻 0 位于数轴 $a_{i}$ 处，而你希望在时刻 $t_{i}$ 以及之后的所有时刻，这个箱子处在数轴的 $b_{i}$ 处。保证序列 $[a_{1}, \dots, a_{n}]$ 和 $[b_{1}, \dots, b_{n}]$ 单调递增。

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

选择任意一个箱子。记其编号为 $i$ ，它目前的位置为 $p_{i}$ 。
选择一个方向 $d \in {\pm 1}$ ，其中 $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

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

Universal Online Judge

UOJ

#955. 【统一省选2025】推箱子