← 返回题单

题单练习双指针

← 上一题下一题 →

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++ 编辑器

输入

输出