#P13083. [NOISG 2017] RMQ

    ID: 12714 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2017Special JudgeNOISG(新加坡)

[NOISG 2017] RMQ

题目背景

译自 NOISG 2017 D.RMQ

题目描述

小 K 有 NN 头奶牛,编号分别为 00N1N-1。这些奶牛以某种未知的顺序排成了一排。

现在给出 QQ 条信息,每条信息包含三个整数 Li,Ri,AiL_i,R_i,A_i,表示区间 [Li,Ri][L_i,R_i] 内编号最小的奶牛的编号为 AiA_i。请你构造一组奶牛的顺序使得其可以满足所有信息。

输入格式

第一行两个正整数 N,QN,Q,分别表示奶牛数和信息数。

接下来 QQ 行,每行三个整数 Li,Ri,AiL_i,R_i,A_i,代表一条信息。

输出格式

一行 NN 个整数表示你构造的奶牛的顺序。如果有多个解,输出任意一个即可。如果无解,输出 NN1-1

5 3
0 2 1
1 3 0
1 4 0
1 4 3 0 2
3 2
0 1 1
1 2 1
-1 -1 -1

提示

样例解释

对于样例 1,请注意这不是唯一满足要求的顺序。

对于样例 2,如果 00 号奶牛在 00 号位置或者 11 号位置,那么区间 [0,1][0,1] 的最小值应为 00 而非 11;如果 00 号奶牛在 22 号位置,那么区间 [1,1][1,1] 的最小值应为 00 而非 11。因此,不存在符合要求的顺序。

评分标准

对于一个测试点:

  • 如果你的输出满足以下要求,你将获得该测试点所有的分数:
    • 输出 NN 个数。
    • 该测试点无解,并且你也判断无解。
    • 该测试点有解,并且你构造的顺序满足所有信息而且没有奶牛编号相同。
  • 如果你的输出满足以下要求,你将获得该测试点 30%30\% 的分数:
    • 输出 NN 个数。
    • 你构造的顺序满足所有信息但是有奶牛编号相同。
  • 否则你将获得该测试点 0%0\% 的分数。

例如,对于样例 2,如果你输出 1 1 1,那么你将获得该点 30%30\% 的分数。

数据范围

本题采用 Subtask\text{Subtask} 捆绑测试。

Subtask\text{Subtask} 分值 N,QN,Q
11 2323 10\le10
22 4444 1000\le1000
33 3333 105\le10^5

对于所有数据,保证 1N,Q1051\le N,Q\le10^50Li,Ri<N0\le L_i,R_i< N0Ai<N0\le A_i< N