P9126 [USACO23FEB] Moo Route II S

题目描述

注意：本题的时间限制为 4 秒，是默认限制的两倍。

Bessie 正在度假！由于最近的技术进步，Bessie 可以通过先进的航班旅行，这些航班甚至可以进行时间旅行。此外，即使存在多个“平行”的 Bessie 同时出现也不会有任何问题。

在这个国家，有 $N$ 个机场，编号为 $1,2,\cdots,N$，以及 $M$ 条时间旅行航班（$1 \leq N,M \leq 200000$）。第 $j$ 条航班从机场 $c_j$ 在时间 $r_j$ 起飞，并在时间 $s_j$ 抵达机场 $d_j$（$0 \leq r_j,s_j \leq 10^9$，$s_j < r_j$ 是可能的）。此外，Bessie 在机场 $i$ 需要停留 $a_i$ 时间（$1 \leq a_i \leq 10^9$）。也就是说，如果 Bessie 乘坐一趟航班在时间 $s$ 抵达机场 $i$，她可以转乘一趟从该机场出发的航班，只要该航班的起飞时间 $r \geq s + a_i$。需要注意的是，停留时间不会影响 Bessie 抵达某机场的实际时间。

Bessie 从城市 $1$ 出发，起始时间为 $0$。对于从 $1$ 到 $N$ 的每个机场，求出 Bessie 最早可以到达该机场的时间。

输入格式

第一行输入包含两个整数 $N$ 和 $M$。

接下来的 $M$ 行描述航班信息。其中第 $j$ 行包含 $c_j, r_j, d_j, s_j$，依次表示航班的起飞机场、起飞时间、降落机场和降落时间。$(1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9)$

接下来的 $1$ 行描述每个机场的停留时间。该行包含 $N$ 个用空格分隔的整数，分别为 $a_1,\cdots,a_N$。

输出格式

输出共 $N$ 行。第 $i$ 行输出 Bessie 最早到达机场 $i$ 的时间；如果无法到达该机场，输出 $-1$。

样例 1 的解释

Bessie 可以按照给定的顺序乘坐第 $3$ 班航班，这使她可以在时间 $0$ 到达机场 $1$ 和机场 $2$，以及在时间 $20$ 到达机场 $3$。

注意，这条路线会两次经过机场 $2$，第一次是在时间 $10-11$，第二次是在时间 $0-1$。

样例 2 的解释

在这个例子中，Bessie 可以乘坐第 $1$ 班航班，在时间 $10$ 抵达机场 $2$。但是，她无法及时赶上第 $2$ 班航班，因为该航班的起飞时间为 $10$，而她需要至少 $1$ 个时间单位来完成停留。

评分标准

• 测试点 $3-5$：对于每个 $j$，$r_j < s_j$，也就是说所有航班的到达时间晚于起飞时间。
• 测试点 $6-10$：$N,M \leq 5000$
• 测试点 $11-20$：无额外限制。

输入输出样例 1

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

0
0
20

输入输出样例 2

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

0
10
-1