fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. const int N=2e5;
  4. vector<vector<int> >arr;
  5. struct data
  6. {
  7. 	int a;
  8. 	int b ;
  9. 	int c ;
  10. 	int ans;
  11. };
  12. data node[4*N+5];
  13. void build(int i , int j , int index)
  14. {
  15. 	if(i==j)
  16. 	{
  17. 		node[index].a=arr[i][0];
  18. 		node[index].b=arr[i][1];
  19. 		node[index].c=arr[i][2];
  20. 		node[index].ans=1;
  21. 		return ;
  22. 	}
  23. 	int mid=(i+j)/2;
  24. 	build(i,mid,2*index);
  25. 	build(mid+1,j,2*index+1);
  26. 	data l=node[2*index];
  27. 	data r=node[2*index+1];
  28. 	if(l.a<r.a&&l.b<r.b&&l.c<r.c)
  29. 	{
  30. 	node[index].ans=node[2*index].ans;
  31. 	}
  32. 	else
  33. 	node[index].ans=l.ans+r.ans;
  34. 	node[index].a=l.a;
  35. 	node[index].b=l.b;
  36. 	node[index].c=l.c;
  37. }
  38. int main ()
  39. {
  40. 	int t;
  41. 	cin >> t ;
  42. 	while(t--)
  43. 	{
  44. 	int n ;
  45. 	cin >> n;
  46. 	for (int i=0;i<n;i++)
  47. 	{
  48. 		int a, b , c;
  49. 		cin >> a >> b >> c;
  50. 		vector<int>temp;
  51. 		temp.push_back(a);
  52. 		temp.push_back(b);
  53. 		temp.push_back(c);
  54. 		arr.push_back(temp);
  55. 	}
  56. 	sort(arr.begin(),arr.end());
  57. 	build(0,n-1,1);
  58. 	cout<<node[1].ans<<"\n";
  59. 	arr.clear();
  60. 	}
  61. }
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin 
1
3
1 2 3
2 3 1
3 1 2
stdout 
3
https://ideone.com/jRewBt
problem NICEDAY, based on SPOJ submission 28221728 (CPP14), 2021-07-20 07:44:43
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!