分数: 600 点
问题陈述
考虑一个长度序列 N 组成 0和 1s, A=(A_1,A_2,\dots,A_N),满足以下条件。
对于每个 i=1,2,\dots,M,至少有 X_i 出现
1其中 A_{L_i}, A_{L_i+1}, \dots, A_{R_i}.
打印一个这样的序列 最少 出现的次数 1s。
总是存在满足约束下的条件的序列。
约束
- 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.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M L_1 R_1 X_1 L_2 R_2 X_2 \vdots L_M R_M X_M
输出
打印序列 A 组成 0和 1s,中间有空格。
A_1 A_2 \dots A_N
必须满足上述所有要求。
示例输入 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,其数量超过了最少的数量 1s,是不可接受的。
示例输入 2
8 2 2 6 1 3 5 3
示例输出 2
0 0 1 1 1 0 0 0