比赛场次 578
比赛名称 4043级2023省选模拟赛8
比赛状态 已结束比赛成绩
开始时间 2023-03-29 18:40:00
结束时间 2023-03-29 22:00:00
开放分组 全部用户
注释介绍 van two
题目名称 Moo Route II
输入输出 mooroutetwo.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分
Gravatarzxhhh AAAAAAAAAAAAAAAAAAAA
2.409 s 14.15 MiB 100
Gravatarムラサメ AAAAAAAAAAAAAAAAAAAA
6.427 s 28.24 MiB 100

Moo Route II

★★☆   输入文件:mooroutetwo.in   输出文件:mooroutetwo.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

Bessie 正在旅游!有 $n$ 个城市和 $m$ 条航线,第 $i$ 条航线有 $(c_i,r_i,d_i,s_i)(1\leq c_i\neq d_i\leq n,0\leq r_i,s_i\leq 10^9)$ 的限制,表示从 $c_i$ 到 $d_i$,最迟 $r_i$ 时进入,$s_i$ 时到达。第 $i$ 个城市有 $a_i$ 的停泊时间,表示 **乘坐航班到达** $i$ 后,需要等待 $a_i$ 的时间后才能继续飞行。问到达每个城市的最早时间?如果不能到达,输出 `-1`。

【输入格式】

第一行两个整数 $n,m$。

接下来 $m$ 行每行四个整数 $c_i,r_i,d_i,s_i$。

接下来一行 $n$ 个整数,表示 $a_i$。

【输出格式】

$n$ 行,第 $i$ 行一个整数表示到达 $i$ 的最早时间,不能到达输出 `-1`。

【样例1输入】

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

【样例1输出】

0
0
20

【样例1解释】


贝茜可以按顺序依次乘坐 $3$ 个给定航班,这可以让它在时间 $0$ 到达机场 $1,2$,在时间 $20$ 到达机场 $3$。

注意,这个行进路线的过程中在机场 $2$ 停留了两次,第一次停留是时间 $10−11$,第二次停留是时间 $0−1$。

【样例2输入】

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

【样例2输出】

0
10
-1

【样例2解释】

在本样例中,贝茜可以乘坐第 $1$ 个航班并于时间 $10$ 到达机场 $2$。

然后它必须在机场 $2$ 停留时间 $1$,因此它无法乘坐第 $2$ 个航班,继而也无法乘坐第 $3$ 个航班。

【数据规模与约定】

测试点 $3-5$: $r_j<s_j$ 对于所有 $j$,即所有航班在起飞后到达。

测试点 $6-10$: $N,M \le 5000$。

$1≤N,M≤2×10^5,1≤c_j,d_j≤N,0≤r_j,s_j≤10^9,s_j<r_j$ 是有可能的。

$1≤a_i≤10^9$。