Tickets

题目描述

Bessie 要去远足！她当前走的步道由 $N$ 个检查点组成，编号为 $1\ldots N$（$1\le N\le 10^5$）。

有 $K$（$1\le K\le 10^5$）张可购买的票。第 $i$ 张票可以在检查点 $c_i$（$1\le c_i\le N$）以价格 $p_i$（$1\le p_i\le 10^9$）购买，并提供对所有检查点区间 $[a_i,b_i]$（$1\le a_i\le b_i\le N$）的通行权限。在进入任意检查点之前，Bessie 必须已经购买了一张允许进入该检查点的票。一旦 Bessie 获得了某个检查点的访问权限，她在未来任意时刻都可以返回该检查点。她可以在任意两个她有访问权限的检查点之间移动，而不管它们的编号是否相差 1。

对每个 $i\in [1,N]$，如果 Bessie 初始仅能访问检查点 $i$，请输出购买通行权限以同时访问检查点 $1$ 和 $N$ 所需的最小总价格。如果无法做到，则输出 $-1$。

输入格式

第一行包含 $N$ 和 $K$。 接下来 $K$ 行中，第 $i$ 行包含四个整数 $c_i$, $p_i$, $a_i$, $b_i$（对每个 $1\le i\le K$）。

输出格式

输出 $N$ 行，每行对应一个检查点。

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
-1
-1
1111
10100
110100
-1

提示

如果 Bessie 从检查点 $i=4$ 开始，那么让 Bessie 购买到检查点 $1$ 和 $N$ 的通行权限的一种方式如下： 在检查点 $4$ 购买第一张票，使 Bessie 获得对检查点 $2$ 和 $3$ 的访问权限。 在检查点 $2$ 购买第三张票，使 Bessie 获得对检查点 $7$ 的访问权限。 返回检查点 $4$ 并购买第二张票，使 Bessie 获得对检查点 $5$ 和 $6$ 的访问权限。 在检查点 $6$ 购买第四张票，使 Bessie 获得对检查点 $1$ 的访问权限。 SCORING: 测试点 1-7 满足 $N,K\le 1000$。 测试点 8-19 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum