#P1712. [NOI2016] 区间

    ID: 743 远端评测题 1000~3000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2016线段树NOI 系列离散化O2优化排序

[NOI2016] 区间

题目描述

在数轴上有 nn 个闭区间从 11nn 编号,第 ii 个闭区间为 [li,ri][l_i,r_i]

现在要从中选出 mm 个区间,使得这 mm 个区间共同包含至少一个位置。换句话说,就是使得存在一个 xx ,使得对于每一个被选中的区间 [li,ri][l_i,r_i],都有 lixril_i \leq x \leq r_i

对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。

区间 [li,ri][l_i,r_i] 的长度定义为 (rili)(r_i-l_i) ,即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案,输出 1-1

输入格式

第一行包含两个整数,分别代表 nnmm

22 到第 (n+1)(n + 1) 行,每行两个整数表示一个区间,第 (i+1)(i + 1) 行的整数 li,ril_i, r_i 分别代表第 ii 个区间的左右端点。

输出格式

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

6 3
3 5
1 2
3 4
2 2
1 5
1 4
2

提示

样例输入输出 1 解释

如图,当 n=6n=6m=3m=3 时,花费最小的方案是选取 [3,5],[3,4],[1,4][3,5],[3,4],[1,4] 这三个区间,它们共同包含了 44 这个位置,所以是合法的。其中最长的区间是 [1,4][1, 4],最短的区间是 [3,4][3, 4],所以它的花费是 (41)(43)=2(4 - 1) - (4 - 3) = 2

数据规模与约定

本题共 20 个测试点,各测试点信息如下表。 | 测试点编号 | n= n= | m= m= | li,ri l_i,r_i | |:-:|:-:|:-:|:-:| | 1 | 20 20 | 9 9 | 0liri100 0 \le l_i \le r_i \le 100 | | 2 | 20 20 | 10 10 | 0liri100 0 \le l_i \le r_i \le 100 | | 3 | 199 199 | 3 3 | 0liri100000 0 \le l_i \le r_i \le 100000 | | 4 | 200 200 | 3 3 | 0liri100000 0 \le l_i \le r_i \le 100000 | | 5 | 1000 1000 | 2 2 | 0liri100000 0 \le l_i \le r_i \le 100000 | | 6 | 2000 2000 | 2 2 | 0liri100000 0 \le l_i \le r_i \le 100000 | | 7 | 199 199 | 60 60 | 0liri5000 0 \le l_i \le r_i \le 5000 | | 8 | 200 200 | 50 50 | 0liri5000 0 \le l_i \le r_i \le 5000 | | 9 | 200 200 | 50 50 | 0liri109 0 \le l_i \le r_i \le 10^9 | | 10 | 1999 1999 | 500 500 | 0liri5000 0 \le l_i \le r_i \le 5000 | | 11 | 2000 2000 | 400 400 | 0liri5000 0 \le l_i \le r_i \le 5000 | | 12 | 2000 2000 | 500 500 | 0liri109 0 \le l_i \le r_i \le 10^9 | | 13 | 30000 30000 | 2000 2000 | 0liri100000 0 \le l_i \le r_i \le 100000 | | 14 | 40000 40000 | 1000 1000 | 0liri100000 0 \le l_i \le r_i \le 100000 | | 15 | 50000 50000 | 15000 15000 | 0liri100000 0 \le l_i \le r_i \le 100000 | | 16 | 100000 100000 | 20000 20000 | 0liri100000 0 \le l_i \le r_i \le 100000 | | 17 | 200000 200000 | 20000 20000 | 0liri109 0 \le l_i \le r_i \le 10^9 | | 18 | 300000 300000 | 50000 50000 | 0liri109 0 \le l_i \le r_i \le 10^9 | | 19 | 400000 400000 | 90000 90000 | 0liri109 0 \le l_i \le r_i \le 10^9 | | 20 | 500000 500000 | 200000 200000 | 0liri109 0 \le l_i \le r_i \le 10^9 |

对于全部的测试点,保证 1mn1 \leq m \leq n1n5×1051 \leq n \leq 5 \times 10^51m2×1051 \leq m \leq 2 \times 10^50liri1090 \leq l_i \leq r_i \leq 10^9