#P11288. [COTS 2020] 定序 Redoslijed

    ID: 10450 传统题 4000ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2300线段树拓扑排序贪心数据结构构造图论

[COTS 2020] 定序 Redoslijed

题目描述

在一块长 N mN\,\mathrm{m} 的木板上画画。木板被从左往右划分成 NN 个格子,每个格子长 1 m1\,\mathrm{m}。

现在已知在木板上涂了 MM 笔,第 ii 笔将第 li∼ril_i\sim r_i 个格子涂成颜色 cic_i。

给定最后涂色后木板的状态,试构造一种操作顺序使得一次操作后木板的状态为给定状态,或报告无解。

输入格式

第一行,两个正整数 N,MN,M。

接下来 MM 行,每行三个整数 li,ri,cil_i,r_i,c_i,描述一个涂色操作。

接下来一行,NN 个整数,第 ii 个整数表示第 ii 个格子最后的颜色 bib_i。特别地,若 bi=0b_i=0,代表 bib_i 未被着色。

输出格式

如果无解,输出 NE\texttt{NE}(克罗地亚语「否」)。

否则第一行输出 DA\texttt{DA}(克罗地亚语「是」);第二行输出一个 1∼M1\sim M 的排列表示涂色顺序。

若有多解,任意均可。

输入输出样例 #1

输入 #1

6 5
3 5 5
1 1 6
1 3 2
1 4 7
4 6 6
6 2 5 5 5 6

输出 #1

DA
4 5 3 1 2

输入输出样例 #2

输入 #2

14 6
6 9 4
12 13 6
2 3 5
1 14 3
5 6 9
9 12 8
3 5 5 3 9 4 4 4 8 8 8 6 6 3

输出 #2

DA
4 5 1 6 2 3

输入输出样例 #3

输入 #3

15 5
7 8 3
10 14 5
4 7 2
3 12 1
5 9 4
0 0 1 2 4 4 3 3 4 5 1 1 5 5 0

输出 #3

NE

说明/提示

对于 100%100\% 的数据,保证:

  • 1≤N,M≤5×1051\le N,M\le 5\times 10^5;
  • 1≤li≤ri≤N1\le l_i\le r_i\le N;
  • 1≤ci≤5×1051\le c_i\le 5\times 10^5;
  • 0≤bi≤5×1050\le b_i\le 5\times 10^5。
子任务编号 N≤N\le 特殊性质 得分
1 1 99 5 5
2 2 5 0005\,000 A 10 10
3 3 5×1055\times 10^5 25 25
4 4 5 0005\, 000 12 12
5 5 5×1055\times 10^5 B 16 16
6 6 32 32
  • 特殊性质 A:cic_i 两两不同。
  • 特殊性质 B:1≤ci≤51\le c_i\le 5。