分数: 900 点
问题陈述
考虑制作一个字符串 s 长度 N 组成 0 和 1,其中 s 必须满足 M 条件。
的 i-第条件用整数表示 L_i 和 R_i (1 \leq L_i < R_i \leq N)。
这意味着应该有相同数量的 0 和 1 之间 L_i-th 和 R_i第个字符(含) s.
查找字典顺序最小的字符串 s 满足所有条件。 可以证明问题的约束条件保证了 s 满足条件。
约束
- 2 \leq N \leq 10^6
- 1 \leq M \leq 200000
- 1 \leq L_i < R_i \leq N
- (R_i-L_i+1) \equiv 0 \mod 2
- (L_i,R_i) \neq (L_j,R_j) (i \neq j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
输出
打印答案。
示例输入 1
4 2 1 2 3 4
示例输出 1
0101
示例输入 2
6 2 1 4 3 6
示例输出 2
001100
示例输入 3
20 10 6 17 2 3 14 19 5 14 10 15 7 20 10 19 3 20 6 9 7 12
示例输出 3
00100100101101001011