/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
0 と 1 のみからなる長さ N の数列 A=(A_1,A_2,\dots,A_N) であって、以下の条件を満たすものを考えます。
すべての i=1,2,\dots,M について、A_{L_i}, A_{L_i+1},\dots ,A_{R_i} に
1が X_i 個以上含まれる
条件を満たす数列 A のうち、含まれる 1 の数が最も少ない例を 1 つ出力してください。
なお、制約のもとで条件を満たす数列 A は必ず存在します。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq \min(2 \times 10^5, \frac{N(N+1)}{2} )
- 1 \leq L_i \leq R_i \leq N
- 1 \leq X_i \leq R_i-L_i+1
- i \neq j ならば (L_i,R_i) \neq (L_j,R_j)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M L_1 R_1 X_1 L_2 R_2 X_2 \vdots L_M R_M X_M
出力
0 と 1 のみからなる数列 A を空白区切りで出力せよ。
A_1 A_2 \dots A_N
数列 A は上記の条件を全て満たさなければならない。
入力例 1
6 3 1 4 3 2 2 1 4 6 2
出力例 1
0 1 1 1 0 1
1 1 0 1 1 0 などの答えも正解です。
0 1 1 1 1 1 などの答えは含まれる 1 の数が最小化されていないので、不正解です。
入力例 2
8 2 2 6 1 3 5 3
出力例 2
0 0 1 1 1 0 0 0
Score : 600 points
Problem Statement
Consider a sequence of length N consisting of 0s and 1s, A=(A_1,A_2,\dots,A_N), that satisfies the following condition.
For every i=1,2,\dots,M, there are at least X_i occurrences of
1among A_{L_i}, A_{L_i+1}, \dots, A_{R_i}.
Print one such sequence with the fewest number of occurrences of 1s.
There always exists a sequence that satisfies the condition under the Constraints.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq \min(2 \times 10^5, \frac{N(N+1)}{2} )
- 1 \leq L_i \leq R_i \leq N
- 1 \leq X_i \leq R_i-L_i+1
- (L_i,R_i) \neq (L_j,R_j) if 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 X_1 L_2 R_2 X_2 \vdots L_M R_M X_M
Output
Print a sequence A consisting of 0s and 1s, with spaces in between.
A_1 A_2 \dots A_N
It must satisfy all the requirements above.
Sample Input 1
6 3 1 4 3 2 2 1 4 6 2
Sample Output 1
0 1 1 1 0 1
Another acceptable output is 1 1 0 1 1 0.
On the other hand, 0 1 1 1 1 1, which has more than the fewest number of 1s, is unacceptable.
Sample Input 2
8 2 2 6 1 3 5 3
Sample Output 2
0 0 1 1 1 0 0 0