P11432 [COCI 2024/2025 #2] 流明 / Blistavost

题目背景

译自 COCI 2024/2025 #2 T4。$\texttt{4s,1G}$。满分为 $120$。

题目描述

数轴的正半轴的整数点上布满了璀璨的水晶灯。起初，它们都是点亮的。

初始时，时刻为 $0$，守卫在原点处。每单位时间，她可以选择向左或者向右移动一单位长度，也可以待在原地。

当守卫在一盏水晶灯所在的位置时，可以选择熄灭这盏水晶灯。熄灭不消耗时间。

有 $n$ 个要求，每个要求形如三元组 $(l_i,r_i,t_i)$，表示：村民需要熄灭区间 $[l_i,r_i]$ 内的水晶灯，而且必须在时刻${}\ge t_i$ 时才能熄灭这个区间内的水晶灯（也就是说，时刻 $\lt t_i$ 时不能熄灭这个区间内任意一盏水晶灯）。

请你计算守卫至少需要多少单位时间才能满足村民的全部要求。

输入格式

第一行，一个正整数 $n$。

接下来 $n$ 行，每行三个正整数 $l_i,r_i,t_i$。

输出格式

输出一行一个正整数，表示答案。

输入输出样例 #1

输入 #1

3
1 1 1
3 3 5
5 5 3

输出 #1

7

输入输出样例 #2

输入 #2

3
1 2 1
1 1 5
1 3 4

输出 #2

6

输入输出样例 #3

输入 #3

3
6 6 6
8 8 7
9 9 9

输出 #3

9

说明/提示

样例解释

样例 $2$ 解释：

时刻 $3$ 时走到 $x=3$ 处，停留一单位时间。

时刻 $4$ 时，熄灭 $x=3$ 的水晶灯。

时刻 $5$ 时，走到 $x=2$ 并熄灭上面的水晶灯。

时刻 $6$ 时，走到 $x=1$ 并熄灭上面的水晶灯。

耗时 $6$ 单位时间。

提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 5\, 000$；
• $1\le l_i\le r_i\le 10^{18}$；
• $1\le t_i\le 10^{18}$。

子任务编号	$n\le$	特殊性质	得分
$1$	$18$	A	$20$
$2$	$5\, 000$	B	$25$
$3$		A	$55$
$4$			$20$

• 特殊性质 A：$l_i=r_i$。
• 特殊性质 B：$l_i=1$。

#5701. 「COCI 2024/2025 #2」Blistavost

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

译自 COCI 2024/2025 Contest #2 T4「Blistavost」

在 Glass Valley 的中心，坐落着一座神秘的星光神庙，那里以收藏像星星一样闪烁的魔法水晶而闻名。每颗水晶都拥有特殊的力量，只要不被触碰，就会发出耀眼的光芒，照亮整个山谷。

神庙守护者每晚的任务是：仅触碰山谷居民指定范围内的水晶，同时满足他们所有的要求。

每位居民的请求都告诉守护者，在他们上床睡觉之前，哪些范围内的水晶必须停止发光，因为他们害怕黑暗。

守护者从神庙入口开始他的旅程，必须仔细协调他的行动以熄灭水晶，使它们在准确的时间停止发光。水晶排列成一条直线，彼此间隔一米（第一颗水晶距离入口一米）。守护者可以以每秒一米的速度移动，并可以在需要时停下。守护者触碰并熄灭一颗水晶所需的时间可以忽略不计。根据居民们的请求，神庙守护者想知道满足所有要求所需的最少秒数（守护者不需要回到起始位置）。

输入格式

第一行是一个整数 $N$ $(1 \leq N \leq 5000)$，表示居民请求的数量。

接下来的 $N$ 行是整数 $l_{i}, r_{i}, t_{i}$ $(1 \leq l_{i} \leq r_{i} \leq 10^{18}, 1 \leq t_{i} \leq 10^{18})$，分别表示水晶范围的左边界、右边界以及居民的就寝时间。

输出格式

在第一行也是唯一一行中，输出守护者满足所有要求所需的最少时间（单位为秒）。

样例 1

输入

3
1 1 1
3 3 5
5 5 3

输出

7

样例 2

输入

3
1 2 1
1 1 5
1 3 4

输出

6

神庙守护者将首先花费 $3$ 秒到达第 $3$ 颗水晶。然后，他将等待 $1$ 秒并熄灭第 $3$ 颗水晶。之后，他将花费 $1$ 秒前往第 $2$ 颗水晶并将其熄灭。最后，他将花费 $1$ 秒到达第 $1$ 颗水晶并将其熄灭。总共，他的旅程将持续 $6$ 秒，这是满足所有请求所需的最短时间。

样例 3

输入

3
6 6 6
8 8 7
9 9 9

输出

9

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$20$	$n \leq 18, l_{i}=r_{i}$，对于所有的 $i=1,2, \ldots, n$
$2$	$25$	$l_{i}=1$，对于所有的 $i=1,2, \ldots, n$
$3$	$55$	$l_{i}=r_{i}$，对于所有的 $i=1,2, \ldots, n$
$4$	$20$	无附加限制