fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX=3e5+7;
  5. int opening[MAX],closing[MAX];
  6. int n,k;
  7. vector<pair<int,int> >v;
  8. vector<pair<int,pair<int,int> > >I;
  9. multiset<int>open,close;
  10.  
  11. void f()
  12. {
  13. int L=0,R=-1,c=0;
  14. int ans=0,op=0;
  15. for(auto j:v)
  16. {
  17. c++;
  18. I.push_back(make_pair(j.first,make_pair(0,c)));
  19. I.push_back(make_pair(j.second,make_pair(1,c)));
  20. }
  21. sort(I.begin(),I.end());
  22. for(auto j:I)
  23. {
  24. int c=j.second.second;
  25. if(j.second.first==0)
  26. {
  27. op++;
  28. open.insert(j.first);
  29. close.insert(closing[c]);
  30. }
  31. if(op>=k)
  32. {
  33. int r=*close.begin();
  34. int l=*open.rbegin();
  35. if(ans<r-l+1)
  36. {
  37. ans=r-l+1;
  38. L=l;
  39. R=r;
  40. }
  41. }
  42. if(j.second.first==1)
  43. {
  44. op--;
  45. auto k=open.find(opening[c]);
  46. open.erase(k);
  47. k=close.find(j.first);
  48. close.erase(k);
  49. }
  50. }
  51. if(ans==0)
  52. {
  53. cout<<0<<endl;
  54. for(int i=1;i<=k;i++)
  55. cout<<i<<" ";
  56. cout<<endl;
  57. }
  58. else
  59. {
  60. cout<<ans<<endl;
  61. c=0;
  62. for(auto j:v)
  63. {
  64. c++;
  65. if(k<=0)
  66. break;
  67. if(L>=j.first&&R<=j.second)
  68. {
  69. cout<<c<<" ";
  70. k--;
  71. }
  72. }
  73. cout<<endl;
  74. }
  75. }
  76.  
  77. int main()
  78. {
  79. ios_base::sync_with_stdio(false);
  80. cin>>n>>k;
  81. for(int i=1;i<=n;i++)
  82. {
  83. int l,r;
  84. cin>>l>>r;
  85. v.push_back(make_pair(l,r));
  86. opening[i]=l;
  87. closing[i]=r;
  88. }
  89. f();
  90. return 0;
  91. }
  92.  
Success #stdin #stdout 0s 5816KB
stdin
Standard input is empty
stdout
0