#P5102. [POI2018]Prawnicy

    ID: 4188 传统题 4000ms 128MiB 尝试: 622 已通过: 215 难度: 5 上传者: 标签>CF1700普及+/提高-排序贪心堆贪心删除最差已选项鸣谢Claris上传试题

[POI2018]Prawnicy

题目描述

定义一个区间 (l,r)(l,r) 的长度为 r−lr-l ,空区间的长度为 00。

给定数轴上 nn 个区间,请选择其中恰好 kk 个区间,使得交集的长度最大。

输入格式

第一行包含两个正整数 n,kn,k,表示区间的数量。

接下来 nn 行,每行两个正整数 l,rl,r,依次表示每个区间。

输出格式

第一行输出一个整数,即最大长度。

第二行输出 kk 个正整数,依次表示选择的是输入中的第几个区间。

若有多组最优解,输出任意一组。

样例

6 3
3 8
4 12
2 6
1 10
5 9
11 12
4
1 2 4

提示

对于 100%100\% 的数据,1≤k≤n≤106,1≤l<r≤1091 \leq k \leq n \leq 10^6,1 \leq l<r \leq 10^9。

样例解释

选择区间 1,2,41,2,4,交集为 [4,8][4,8]。

Source

鸣谢Claris上传试题