← 返回题目

题库练习参观博物馆

← 上一题下一题 →

A5307 | $参观博物馆$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

博物馆在接下来的 $n$ 天中举办了 $k$ 场展览，第 $i$ 场展览在第 $l_i$ 到 $r_i$ 天之间展出（包含两端）。 现在有一位**摄影师**和一位**评论家**要参观博物馆，每人参观 $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)$。

输出格式

输出两个整数，分别表示**摄影师**和**评论家**的最佳起始日期。注意，这俩人的的参观日期必须都在 $1$ 和 $n$ 之间。

输入输出样例

输入 #1

输出 #1

1 4

C++ 编辑器

输入

输出