/ 
Time Limit: 5 sec / Memory Limit: 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