実行時間制限: 5 sec / メモリ制限: 1024 MB
配点 : 900 点
問題文
0
, 1
からなる長さ N の文字列 s を作ることを考えます.
ここで,s は M 個の条件を満たす必要があります.
i 番目の条件は整数 L_i,R_i (1 \leq L_i < R_i \leq N) で表されます.
これは,s の L_i 文字目から R_i 文字目までを見たときに,そこに含まれる 0
の個数と 1
の個数が等しい必要があることを意味します.
すべての条件を満たす中で辞書順最小の 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
Score : 900 points
Problem Statement
Consider making a string s of length N consisting of 0
and 1
, where s must satisfy M conditions.
The i-th condition is represented by integers L_i and R_i (1 \leq L_i < R_i \leq N).
This means that there should be equal numbers of 0
and 1
between the L_i-th and R_i-th characters (inclusive) of s.
Find the lexicographically smallest string s that satisfies all conditions. It can be proved that the Constraints of the problem guarantee the existence of s that satisfies the conditions.
Constraints
- 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)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
Output
Print the answer.
Sample Input 1
4 2 1 2 3 4
Sample Output 1
0101
Sample Input 2
6 2 1 4 3 6
Sample Output 2
001100
Sample Input 3
20 10 6 17 2 3 14 19 5 14 10 15 7 20 10 19 3 20 6 9 7 12
Sample Output 3
00100100101101001011