原题提交页面

点我进入提交页面

题目描述

你需要构造出一个长度为 $n$ 的 $01$ 序列，满足 $m$ 个限制 $(l_i,r_i,x_i)$：在 $[l_i,r_i]$ 这段区间内，序列上 $1$ 的个数不小于 $x_i$。你需要保证你的方案中包含 $1$ 的个数最小。

数据保证有解。

输入格式

第一行输入 $N$ $M$

接下来 $M$ 行每行输入三个整数 $L_i$ $R_i$ $X_i$

输出格式

输出一个空格隔开的 $01$ 序列。

6 3
1 4 3
2 2 1
4 6 2

0 1 1 1 0 1

8 2
2 6 1
3 5 3

0 0 1 1 1 0 0 0

提示

数据范围

• $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)$ 如果 $i \neq j$ 。
• 输入值均为整数。

样例 1 解释

另一个可接受的输出是 1 1 0 1 1 0。

另一方面，0 1 1 1 1 1 的 $1$ 个数多于最少的 $1$ 个数，是不可接受的。