NZIC 2026 Round 1（新西兰信息学竞赛 2025 第一轮）

E.Safe Crossings（安全过马路）

输入： 标准输入（stdin） 输出： 标准输出（stdout） 内存限制： 256 MB 时间限制： 4.0 秒

• problem statement
• submit
• submissions

---

题目描述

你面临着一个挑战：穿过一条有 (M) 条车道的马路。

道路上车流繁忙，而所有车道中一共只有 (N) 个可以让你安全穿过的交通空隙。每个空隙都有一个开始时间和结束时间。由于你事先在道路上安装了摄像头，所以你知道这些时间。

具体来说，如果第 (l) 条车道上有一个空隙，其开始时间和结束时间分别为：

$$s,\ e$$

那么在以下这些时刻：

$$s,\ s+1,\ s+2,\dots,e-2,e-1$$

这条车道上都存在一个交通空隙，因此你可以安全地处在这条车道上。

需要注意：

在恰好等于结束时间 (e) 的时刻，已经不安全了。

---

你从时间：

$$0$$

开始，位于第 1 条车道之前。

每经过 1 秒，你可以选择以下两种操作之一：

• 向前移动到下一条车道，并在下一秒到达；
• 原地等待 1 秒。

你只能在某条车道存在交通空隙时处于这条车道中。

你不能：

• 向后移动；
• 沿着车道方向移动。

需要注意：

如果当前车道的空隙恰好在某一时刻结束，而下一条车道的空隙恰好在同一时刻开始，那么你是可以在这一时刻完成两条车道之间的移动的。

---

你关心的是：

你究竟能够多“安全”地穿过这条马路。

具体来说，在你过马路过程中的任意时刻，如果你正位于某一个交通空隙中，那么这一时刻的安全值定义为：

距离当前这个交通空隙结束，还剩多少个时间单位。

整个过马路过程的总体安全值，定义为：

过马路过程中所有时刻安全值的最小值。

如果根本无法穿过马路，则总体安全值定义为：

$$0$$

---

请注意：

如果你使用 Python，并收到 Time Limit Exceeded，可能需要使用语言：

Python 3.6 (PyPy 7.3)

进行提交。

---

输入格式

第一行包含两个用空格分隔的整数：

N M

接下来有 (N) 行。

第 (i) 行包含三个用空格分隔的整数：

l_i s_i e_i

表示：

在第 (l_i) 条车道上，从时间 (s_i) 开始，到时间 (e_i) 之前，都存在一个交通空隙。

也就是说，这个空隙对应的安全时间区间是：

$$[s_i,e_i)$$

注意：

输入中的这些交通空隙没有保证按照任何顺序给出。

---

输出格式

输出一个整数：

你能够达到的最大总体安全值。

如果无法穿过马路，则输出：

0

---

数据范围

$$1\le N\le100000$$ $$1\le M\le100000$$

每一条车道至少有一个交通空隙。

对于所有：

$$0\le i<N$$

都有：

$$1\le l_i\le M$$

以及：

$$0\le s_i<e_i\le100000000$$

同一条车道上的交通空隙不会相交或重叠。

也就是说，如果：

$$l_i=l_j$$

且：

$$i\ne j$$

那么：

$$s_i\ne s_j$$

并且如果：

$$s_i<s_j$$

则一定有：

$$e_i<s_j$$

也就是说，同一车道上的两个空隙之间一定完全分离。

---

子任务

• 子任务 1（10%）：

$$M=1$$

也就是说，只有一条车道。

• 子任务 2（20%）：

每条车道都只有一个交通空隙。

• 子任务 3（20%）：

$$N\le1000$$

并且对于所有空隙：

$$e_i-s_i\le100$$

• 子任务 4（20%）：

$$N\le1000$$

• 子任务 5（30%）：

没有额外限制。

---

样例 1 说明

一种可行的过马路方案是：

先等待到时间：

$$2$$

然后进入第 1 条车道，并在时间：

$$3$$

到达第 1 条车道。

接下来一直等待到时间：

$$6$$

然后向前移动到第 2 条车道，并在时间：

$$7$$

到达第 2 条车道。

随后离开马路。

这条路线的安全值为：

$$\min(9-6,\ 12-7)$$

即：

$$\min(3,5)=3$$

而这已经是能够达到的最大值。

因此答案为：

3

---

样例输入 1

3 2
2 7 12
1 3 9
2 1 6

样例输出 1

3

---

样例输入 2

2 2
1 2 3
2 3 5

样例输出 2

1

---

样例输入 3

2 2
1 4 6
2 1 5

样例输出 3

0

测试点编号	数据层级	N, M	特殊性质	覆盖点与设计目的	标准答案
1	弱数据	1, 1	单车道、最小规模	检查首次进入时间至少为 1，以及安全区间端点判断	1
2	正常数据	3, 3	每车道一个空隙	必须在前一车道等待后再进入下一车道，检查多车道区间传播	4
3		8, 4	输入乱序、每车道多个空隙	检查空隙排序、多路径选择、无效短空隙和干扰空隙	20
4	边界数据	3, 3	中间车道无法到达	第一、二车道时间相距过大，任何正安全值均无法通过，检查答案为 0	0
5	极限数据	2, 2	大时间值	实际可行安全值超过程序二分上界，检查答案被限制为 100000000	100000000