A5307. 参观博物馆
编程题
普及-
知识点
题目描述
博物馆在接下来的 $n$ 天中举办了 $k$ 场展览，第 $i$ 场展览在第 $l_i$ 到 $r_i$ 天之间展出（包含两端）。
现在有一位**摄影师**和一位**评论家**要参观博物馆，每人参观 $d$ 天，且起始日期必须在 $1$ 到 $n−d+1$ 之间。
- **摄影师**希望他的参观期尽可能多地举办**不同展览**（即参观区间与尽可能多的展览重叠）；
- **评论家**希望她的参观期尽可能**避开展览**（重叠数量最少）。
为两人参观寻找合适的起始日期，如有多个满足要求的起始日期，选择**最早**的那个。
现在有一位**摄影师**和一位**评论家**要参观博物馆，每人参观 $d$ 天，且起始日期必须在 $1$ 到 $n−d+1$ 之间。
- **摄影师**希望他的参观期尽可能多地举办**不同展览**（即参观区间与尽可能多的展览重叠）；
- **评论家**希望她的参观期尽可能**避开展览**（重叠数量最少）。
为两人参观寻找合适的起始日期，如有多个满足要求的起始日期，选择**最早**的那个。
输入格式
- 第一行：三个整数 $n,d,k(1\le n \le 10^5,1\le d,k \le n)$。
- 接下来 $k$ 行，每行两个整数 $l_i,r_i(1 \le l_i \le r_i \le n)$。
- 接下来 $k$ 行，每行两个整数 $l_i,r_i(1 \le l_i \le r_i \le n)$。
输出格式
输出两个整数，分别表示**摄影师**和**评论家**的最佳起始日期。注意，这俩人的的参观日期必须都在 $1$ 和 $n$ 之间。
输入输出样例
输入 #1
7 2 3 1 2 1 3 6 7
输出 #1
1 4
说明/提示
- 在第一个测试样例中，可以发现摄影师能遇到最多两个不同展览，在参观日期区间为 $[1,2]$ 时有两个不同展览，且起始日期 $1$ 最早，评论家在区间 $[4,5]$ 时参观可以避开所有展览。
- 对于 $40\%$ 的数据，$1\le n \le 5000$。
- 对于另外 $60\%$ 的数据，$n \ge 10000$。
- 对于 $100\%$ 的数据，$1\le n \le 10^5,1\le d,k \le n,1 \le l_i \le r_i \le n$。
- 对于 $40\%$ 的数据，$1\le n \le 5000$。
- 对于另外 $60\%$ 的数据，$n \ge 10000$。
- 对于 $100\%$ 的数据，$1\le n \le 10^5,1\le d,k \le n,1 \le l_i \le r_i \le n$。