← 返回题目列表

AtCoder · abc216_g

G. 01序列

中文机器翻译题面 查看原题

分数: 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