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

Solution

把线段按左端点排序，从左到右扫一遍。

考虑以当前区间的左端点为答案的左端点，右端点肯定是已经扫过的前$k$大的右端点的最小值。

开个堆随便维护一下。

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define N (1000009) 7 using namespace std; 8  9 struct Node{
   int l,r,id;}a[N];10 int n,k,l,r,ans,x,y;11 priority_queue
          
           
            ,greater
            
              >q;12 13 inline int read()14 {15 int x=0,w=1; char c=getchar();16 while (c<'0' || c>'9') { if (c=='-') w=-1; c=getchar();}17 while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();18 return x*w;19 }20 21 bool cmp(Node a,Node b)22 {23 return a.l
             
              k) q.pop();39 if (q.size()==k && q.top()-a[i].l>ans)40 ans=q.top()-a[i].l, x=a[i].l, y=q.top();41 }42 printf("%d\n",ans);43 for (int i=1; i<=n; ++i)44 if (a[i].l<=x && a[i].r>=y)45 {46 printf("%d ",a[i].id);47 k--;48 if (!k) break;49 }50 51 }