fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/uxJXw0
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!