#P13083. [NOISG 2017] RMQ
[NOISG 2017] RMQ
题目背景
译自 NOISG 2017 D.RMQ。
题目描述
小 K 有 头奶牛,编号分别为 至 。这些奶牛以某种未知的顺序排成了一排。
现在给出 条信息,每条信息包含三个整数 ,表示区间 内编号最小的奶牛的编号为 。请你构造一组奶牛的顺序使得其可以满足所有信息。
输入格式
第一行两个正整数 ,分别表示奶牛数和信息数。
接下来 行,每行三个整数 ,代表一条信息。
输出格式
一行 个整数表示你构造的奶牛的顺序。如果有多个解,输出任意一个即可。如果无解,输出 个 。
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,如果 号奶牛在 号位置或者 号位置,那么区间 的最小值应为 而非 ;如果 号奶牛在 号位置,那么区间 的最小值应为 而非 。因此,不存在符合要求的顺序。
评分标准
对于一个测试点:
- 如果你的输出满足以下要求,你将获得该测试点所有的分数:
- 输出 个数。
- 该测试点无解,并且你也判断无解。
- 该测试点有解,并且你构造的顺序满足所有信息而且没有奶牛编号相同。
- 如果你的输出满足以下要求,你将获得该测试点 的分数:
- 输出 个数。
- 你构造的顺序满足所有信息但是有奶牛编号相同。
- 否则你将获得该测试点 的分数。
例如,对于样例 2,如果你输出 1 1 1
,那么你将获得该点 的分数。
数据范围
本题采用 捆绑测试。
分值 | ||
---|---|---|
对于所有数据,保证 ,,。