分数: 700 点
问题陈述
有一个整数序列 x = (x_1, \ldots, x_N),初始化为 x_1 = \cdots = x_N = 0.
您将执行 M 对此整数序列进行操作。在 i-th 操作,给你一个整数对 (L_i, R_i) 这样 1 \leq L_i \leq R_i \leq N,并且您必须执行 正好一个 以下三个操作:
- 操作 0:什么都不做。此操作的成本为 0.
- 操作 1:对于每个整数 j 与 1 \leq j \leq N,如果 L_i \leq j \leq R_i 成立,设置 x_j = 1。此操作的成本为 1.
- 操作 2:对于每个整数 j 与 1 \leq j \leq N,如果 L_i \leq j \leq R_i 不成立,设置 x_j = 1。此操作的成本为 1.
你的目标是 x_1 = \cdots = x_N = 1 坚持到底。确定这个目标是否能够实现。如果可以实现,请提出一种实现该目标的方法,使总运营成本最小化。
约束
- 1 \leq N \leq 1000000
- 1 \leq M \leq 200000
- 1 \leq L_i \leq R_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M L_1 R_1 \vdots L_M R_M
输出
如果目标无法实现,则打印 -1.
如果目标可以实现,请按照以下格式打印实现该目标的一种方法,其中操作的总成本最小化,其中 K 是运营的最小总成本,并且 \mathrm{op}_i 是操作类型(0, 1,或 2) 选择为 i第次操作。
K
\mathrm{op}_1 \cdots \mathrm{op}_M
如果有多种方法可以最小化总成本,则打印其中任何一种都可以。
示例输入 1
5 4 2 4 3 5 1 4 2 5
示例输出 1
2 2 0 1 0
在示例输出中, x 更改如下:
- 最初, x = (0,0,0,0,0).
- 在第一次操作中,操作 执行 2 。 x_1 和 x_5 变为 1,所以 x = (1,0,0,0,1).
- 在第二次操作中,操作 0 。 x 仍然存在 (1,0,0,0,1).
- 在第三次操作中,操作 1 。 x_1, x_2, x_3, x_4 变为 1,所以 x = (1,1,1,1,1).
- 在第四次操作中,操作 0 。 x 仍然存在 (1,1,1,1,1).
示例输入 2
5 4 1 3 1 5 2 4 3 5
示例输出 2
1 0 1 0 0
示例输入 3
5 2 1 3 2 5
示例输出 3
2 1 1
示例输入 4
5 2 1 3 2 4
示例输出 4
-1