fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. struct node
  8. {
  9. 	int x,y;
  10. 	node(int x1,int y1)
  11. 	{
  12. 		x=x1;
  13. 		y=y1;
  14. 	}
  15. };
  16.  
  17. bool comp(node*a,node*b)
  18. {
  19. 	if(a->y == b->y)
  20. 	{
  21. 		return a->x < b->x;	
  22. 	}
  23. 	else
  24. 	{
  25. 		return a->y < b->y;
  26. 	}
  27. }
  28.  
  29. int main() {
  30.  
  31. 	int n,k;
  32. 	cin>>n>>k;
  33.  
  34. 	vector<node*> V;
  35. 	for(int i=0;i<n;i++)
  36. 	{
  37. 		int x,y;
  38. 		cin>>x>>y;
  39. 		V.push_back(new node(x,y));
  40. 	}
  41.  
  42. 	sort(V.begin(),V.end(),comp);
  43.  
  44. 	multiset<int> ms;
  45. 	int cnt=0;
  46. 	for(int i=0;i<n;i++)
  47. 	{
  48. 		if(ms.size() == 0)
  49. 		{
  50. 			ms.insert(-1*V[i]->y);
  51. 		}
  52. 		else
  53. 		{
  54. 			auto t = ms.lower_bound(-1*V[i]->x);
  55. 			if(t != ms.end())
  56. 			{
  57. 				//cout<<"t = "<<*t<<endl;
  58. 				ms.erase(t);
  59. 				ms.insert(-1*V[i]->y);
  60. 			}
  61. 			else if(t == ms.end() && ms.size() < k)
  62. 			{
  63. 				//cout<<"t = "<<*t<<endl;
  64. 				ms.insert(-1*V[i]->y);
  65. 			}
  66. 			else
  67. 			{
  68. 				cnt++;
  69. 			}
  70. 		}
  71. 		//cout<<"V["<<i<<"]=("<<V[i]->x<<","<<V[i]->y<<") "<<"ms.size()="<<ms.size()<<" cnt="<<cnt<<endl;
  72. 	}
  73.  
  74. 	cout<<n-cnt<<endl;
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 2
1 5
8 10
3 6
2 5
6 9
stdout
copy 
4
https://ideone.com/pjrI94
language:
C++14 (gcc 8.3)
created:
5 days 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!