IOI 大学的学生们生活在一个冷酷的竞争社会中,他们不以名字相称,而是以考试排名相称。大学里有 $N$ 名学生,对于每个 $0 \le i \le N - 1$,编号为 $i$ 的学生在期中考试中排名第 $i + 1$。
为了准备期末考试,学生们自发组成了辅导小组。每个辅导小组可以用两个整数 $0 \le L \le R \le N - 1$ 来表示,这意味着除了编号在 $L$ 到 $R$ 之间的学生外,其余所有学生都属于该小组。
一天早上,IOI 大学的全体学生都收到了一封邮件,称“至少存在一个辅导小组”。我们将这一天称为第 1 天。从第 $d \ge 1$ 天的晚上开始,将发生以下情况:
- 如果某位学生在第 $d$ 天早上之后推断出存在一个将自己排除在外的辅导小组,该学生会感到不公,并在第 $d$ 天晚上结束前提交申诉。一旦收到申诉,所有辅导小组的活动将在第 $d + 1$ 天早上到来前终止。
- 如果没有任何学生推断出存在一个将自己排除在外的辅导小组,则不会收到申诉,辅导小组的活动将在第 $d + 1$ 天早上继续进行。通过这一点,所有学生都会获得一个共同信息:“没有人在这第 $d$ 天提交申诉”。
除此之外,学生们不会以任何方式分享信息。也就是说,他们只能知道自己所属的辅导小组、每个小组的成员以及是否有人提交了申诉。学生总是会根据自己掌握的信息推断出所有可能的命题,并且不会根据自己掌握的信息推断出可能错误的命题。
你是 IOI 大学的外部人士,与所有学生关系密切,了解所有的辅导小组及其成员。给定关于 $M$ 个辅导小组的所有信息,请编写一个程序,求出提交申诉的日期 $k$,以及在第 $k$ 天提交申诉的学生编号。如果永远不会收到申诉,则返回 $-1$。
请注意,关于小组数量 $M$、每个小组的成员、整个问题及子任务的限制、所有小组都是排除特定范围编号学生的形式等所有信息,只有作为外部人士的你才知道,每个学生对此一无所知。
函数列表及定义
你需要实现以下函数:
pair<int, vector<int> > complaint(int N, vector<int> L, vector<int> R)
- $L, R$: 大小为 $M$ 的整数数组。对于所有 $0 \le i \le M - 1$,第 $i$ 个辅导小组仅由编号小于 $L[i]$ 或大于 $R[i]$ 的学生组成。
- 该函数应返回一个由整数 $k$ 和大小不超过 $N$ 的整数数组 $V$ 组成的序对。$k$ 是提交申诉的日期,$V$ 应该包含在第 $k$ 天提交申诉的学生编号,并按升序排列。如果永远不会收到申诉,则 $k$ 应为 $-1$,$V$ 应为空数组。
提交的源代码中不得执行任何输入输出函数。
数据范围
- $1 \le N \le 250\,000$
- $1 \le M \le 250\,000$
- 对于所有 $0 \le i \le M - 1$,满足 $0 \le L[i] \le R[i] \le N - 1$
子任务
- (12分) $N, M \le 10$
- (6分) 对于所有 $0 \le i \le M - 1$,满足 $L[i] = R[i]$。
- (15分) $N, M \le 2\,500$
- (10分) 对于所有 $0 \le i, j \le M - 1$,区间 $[L[i], R[i]]$ 和 $[L[j], R[j]]$ 要么不相交,要么相互包含。即如果 $L[i] < L[j]$,则满足 $R[i] < L[j]$ 或 $R[j] \le R[i]$。
- (18分) 对于所有 $0 \le i \le M - 2$,满足 $L[i] < L[i + 1]$ 且 $R[i] < R[i + 1]$。
- (39分) 无额外限制。
样例
样例 1
考虑 $N = 6, M = 3, L = [1, 2, 3], R = [4, 5, 3]$ 的情况。
评测程序调用如下:
complaint(6, [1, 2, 3], [4, 5, 3])
由于 3 号学生被所有辅导小组排除在外,他在第一天就提交了申诉。由于其他学生在第一天没有提交申诉,函数应返回 $k = 1$ 和 $V = [3]$ 组成的序对 $(1, [3])$。
样例 2
考虑 $N = 10, M = 4, L = [1, 4, 8, 2], R = [4, 7, 9, 6]$ 的情况。
评测程序调用如下:
complaint(10, [1, 4, 8, 2], [4, 7, 9, 6])
函数应返回 $k = 2$ 和 $V = [4, 8, 9]$ 组成的序对 $(2, [4, 8, 9])$。
样例 3
考虑 $N = 5, M = 1, L = [0], R = [4]$ 的情况。
评测程序调用如下:
complaint(5, [0], [4])
该辅导小组不包含任何学生。(是谁创建了这样的辅导小组?)
函数应返回 $k = 1$ 和 $V = [0, 1, 2, 3, 4]$ 组成的序对 $(1, [0, 1, 2, 3, 4])$。
Sample grader
Sample grader 按以下格式接收输入:
- 第 1 行:$N \ M$
- 第 $2 + i$ 行 ($0 \le i \le M - 1$):$L[i] \ R[i]$
Sample grader 输出以下内容:
- 第 1 行:
complaint函数返回的值 $k$ - 第 2 行:
complaint函数返回的值 $V$ 的元素,以空格分隔。
请注意,Sample grader 可能与实际评测中使用的评测程序不同。