P14595 [COCI 2025/2026 #2] 集训 / Dodatna

题目背景

本题满分 $70$。

题目描述

有 $n$ 名学生，第 $i$ 名学生从每天的第 $l_i$ 毫秒初到每天的第 $r_i$ 毫秒初（第 $(r_i-1)$ 毫秒末）在学校内。

现在要选择一段连续的时间上 OI 课，要求是：

• 所有上课的学生在上课时间内必须全程在学校。
• 至少有 $k$ 人上课。

请输出 OI 课能持续的最长时间（单位：毫秒）。特别地，若无解，输出 $0$。

输入格式

第一行，两个正整数 $n,k$（$1\le n,k\le 3\times 10^5$）。

接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$（$1\le l_i\lt r_i\le 86\, 400\, 000$）。

输出格式

输出一行一个非负整数，表示答案。

特别地，若无解，输出 $0$。

输入输出样例 #1

输入 #1

5 1
1 3
1 4
1 5
1 6
1 7

输出 #1

6

输入输出样例 #2

输入 #2

5 2
6 10
8 14
5 9
5 6
4 6

输出 #2

3

说明/提示

样例解释

样例二解释：在第 $6,7,8$ 毫秒上课，一共可以上 $3$ 毫秒。

子任务

• $\text{Subtask 1 (13 pts)}$：$k=1$；
• $\text{Subtask 2 (27 pts)}$：$1\le n\le 1000$，$k=2$；
• $\text{Subtask 3 (11 pts)}$：$r_i\le 100$；
• $\text{Subtask 4 (19 pts)}$：无额外限制。