#3192. 选点

选点

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目限制

2000 ms 256 M

题目描述

MM 个互不相交的区间( 1M1051 \le M \le 10^5 ),左右端点均为整数(区间包括左右端点),在这些区间内选择 NN2N1052 \le N \le 10^5 )个整点(坐标为整数),使得任意相邻两点之间的最小距离尽可能远,问这个最远的距离是多少?

输入格式

第一行:两个数 NNMM ,分别代表点的数量和区间的数量。 以下 MM 行:每行两个整数 aabb ,对应区间的左右端点,其中 0ab1e180\le a\le b\le 1e18 。 数据保证任意两个区间都不重合。

输出格式

输出可能的最远的距离是多少。

数据范围

对于 10%10\% 的数据, 1M5,2N51 \le M \le 5, 2 \le N \le 5

对于 20%20\% 的数据, 1M1000,2N10001 \le M \le 1000, 2 \le N \le 1000

对于 100%100\% 的数据, 1M105,2N105,0ab10181 \le M \le 10^5, 2 \le N \le 10^5, 0 \le a \le b \le 10^{18}

输入样例 1

5 3
0 2
4 7
9 9

输出样例 1

2

J组赛前模拟7 20241001

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-10-5 16:00
结束于
2024-10-6 4:00
持续时间
12 小时
主持人
参赛人数
75