AT_arc045_b.[ARC045B] ドキドキデート大作戦高橋君
提高+/省选-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
高桥君的心跳约会大作战
高桥君在读的学校即将进行一次大扫除。学校中有N个教室,分别编号为 1,2,3,…,N 。这些教室排成了一排。
高桥君的学校中共有含高桥君在内的 M 个学生,需要扫除的连续教室区间(称为扫除区间)有 M 个。但是,还没有决定由哪个学生来负责哪个扫除区间。不同的学生负责不同的扫除区间,每个学生必须打扫被分配到的所有教室。 1 个教室可能被多个扫除区间包含。
高桥君突然发现,大扫除当天他正好与女同学有约会。无论怎么样高桥君都不想毁掉这次约会,所以只能把大扫除翘掉了。但是高桥君很在意自己会不会暴露:高桥君负责的教室中如果有任何教室没有被打扫,高桥君就会暴露。
你的任务是:替高桥君找出就算翘掉扫除也不会暴露的所有扫除区间。
另外,这所学校里的学生们都非常勤奋努力,故假定除高桥君外的所有人都不会缺席大扫除。
输入格式
输入按以下标准:
N M
s1 t1
s2 t3
:
sM tM
- 第一行为两个整数 N(1≤N≤300,000) 和 M(1≤M≤100,000) ,分别表示学校的教室数和学生数。
- 接下来的 M 行,分别给出 M 个扫除区间。这其中的第 i(1≤i≤M) 行给出表示第 i 个扫除区间的整数 si,ti(1≤si≤ti≤N) 。这表示某个学生需要打扫从 si 到 ti 的所有教室。
- 可能有多个完全相同的区间。
- 任意教室至少被一个扫除区间包含。
输出格式
第一行:输出即使翘掉扫除也不会暴露的扫除区间个数 k 。
接下来 k 行,输出这些区间的编号(升序排列)。最后一行的末尾需换行。
部分分
对于 30% 的数据:
- 对于任意的教室 i(1≤i≤N) ,包含这个教室的扫除区间的个数最大为 2 。
样例1解释
当高桥君负责第 2,5 个扫除区间时不会暴露。具体来说:
- 当高桥君负责第 2 个扫除区间时,第 5 个扫除区间包含了教室 5 所以不会暴露。
- 当高桥君负责第 5 个扫除区间时,第 2 个扫除区间包含了教室 5 ,且第 3 个扫除区间包含了教室 6 ,所以不会暴露。
然而,当高桥君负责第 1,3,4 个扫除区间时,会暴露。具体来说:
- 当高桥君负责第 1 个扫除区间时,教室 1,2,3,4 没有被扫除,故暴露了。
- 当高桥君负责第 3 个扫除区间时,教室 7,8 没有被扫除,故暴露了。
- 当高桥君负责第 4 个扫除区间时,教室 9,10 没有被扫除,故暴露了。
(个人认为第 2,3 个样例解释是没有必要的)
输入输出样例
输入#1
10 5 1 4 5 5 6 8 9 10 5 6
输出#1
2 2 5
输入#2
3 6 1 1 1 1 2 2 2 2 3 3 3 3
输出#2
6 1 2 3 4 5 6
输入#3
10 3 1 4 2 6 6 10
输出#3
0
输入解题思路,AI测评打分。不知道怎么写?