A6163 | $「USACO 2021.12 Platinum」Tickets$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Bessie 正在参加远足旅行！她当前正在旅行的路线由编号为 $1\dotsN$（$1\leqN\leq10^5$）的 $N$ 个检查点组成。 有 $K$（$1\leqK\leq10^5$）张票可供购买。第 $i$ 张票可以在检查站 $c_i$（$1\leqc_i\leqN$）以 $p_i$（$1\leqp_i\leq10^9$）的价格购得，并且可以用其进入所有检查站 $[a_i,b_i]$（$1\leqa_i\leqb_i\leqN$）。在进入任何检查站之前，Bessie 必须已购买一张允许其进入该检查站的票。一旦 Bessie 可以前往某一检查站，她就可以在未来的任何时候回到该检查站。 对于每一个 $i\in[1,N]$，如果 Bessie 最初只能进入检查点 $i$，输出使得可以进入检查点 $1$ 和 $N$ 所需的最低总价。如果无法这样做，输出 $-1$。

输入的第一行包含 $N$ 和 $K$。 以下 $K$ 行，对于每一个 $1\leqi\leqK$，第 $i$ 行包含四个整数 $c_i$，$p_i$，$a_i$ 和 $b_i$。

输出 $N$ 行，每行输出一个检查点的答案。

输入 #1

7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6

输出 #1

C++ 编辑器

输入

输出