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