F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 5102. -- [POI2018]Prawnicy

5102: [POI2018]Prawnicy

Time Limit: 20 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 517  Solved: 225
[Submit][Status][Discuss]

Description

定义一个区间(l,r)的长度为r-l,空区间的长度为0。
给定数轴上n个区间,请选择其中恰好k个区间,使得交集的长度最大。

Input

第一行包含两个正整数n,k(1<=k<=n<=1000000),表示区间的数量。
接下来n行,每行两个正整数l,r(1<=l<r<=10^9),依次表示每个区间。

Output

第一行输出一个整数,即最大长度。
第二行输出k个正整数,依次表示选择的是输入文件中的第几个区间。
若有多组最优解,输出任意一组。

Sample Input

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

Sample Output

4
1 2 4

HINT

Source

鸣谢Claris上传试题

[Submit][Status][Discuss]

HOME Back