fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <set>
  6. #define mp make_pair
  7. #define heap priority_queue
  8. using namespace std;
  9. const int maxn = 40000;
  10. const int maxh = 100;
  11. int n,l[maxn+1],r[maxn+1],maxi,x[maxn*maxh+1],y[maxn*maxh+1],c[maxn*maxh+1],vt[maxn+1];
  12. void enter()
  13. {
  14. 	heap <pair<int,int*> > x;
  15. 	set <int> s;
  16. 	cin >> n;
  17. 	for (int i=1; i<=n; i++)
  18. 	cin >> l[i] >> r[i];
  19. 	for (int i=1; i<=n; i++)
  20. 	{
  21. 		x.push(mp(l[i],&l[i]));
  22. 		x.push(mp(r[i],&r[i]));
  23. 		s.insert(l[i]);
  24. 		s.insert(r[i]);
  25. 	}
  26. 	int pre=-1;
  27. 	int i=s.size()+1;
  28. 	maxi=i-1;
  29. 	while (!x.empty())
  30. 	{
  31. 		pair<int,int*> y=x.top();
  32. 		if (y.first!=pre) 
  33. 		{
  34. 			pre=y.first;
  35. 			i--;
  36. 		}
  37. 		*y.second=i;
  38. 		x.pop();
  39. 	}
  40. 	/*for (int i=1; i<=n; i++)
  41. 	cout << l[i] << ' ' << r[i] << '\n';
  42. 	cout << '\n';*/
  43. }
  44. void init(int i,int l, int r)
  45. {
  46. 	x[i]=l;
  47. 	y[i]=r;
  48. 	c[i]=0;
  49. 	if (l!=r)
  50. 	{
  51. 		int mid=(l+r)/2;
  52. 		init(i*2,l,mid);
  53. 		init(i*2+1,mid+1,r);
  54. 	}
  55. 	else vt[l]=i;
  56. }
  57. void update(int i, int l, int r, int co)
  58. {
  59. 	if ((l<=x[i]) and (y[i]<=r)) c[i]=co;
  60. 	else
  61. 	if (!((y[i]<l) or (x[i]>r)))
  62. 	{
  63. 		update(i*2,l,r,co);
  64. 		update(i*2+1,l,r,co);
  65. 	}
  66. }
  67. int get(int i)
  68. {
  69. 	if (i==1) return c[i];
  70. 	else
  71. 	return max(c[i],get(i/2));
  72. }
  73. void solve()
  74. {
  75. 	set <int> s;
  76. 	init(1,1,maxi);
  77. 	for (int i=1; i<=n; i++)
  78. 	update(1,l[i],r[i],i);
  79. 	for (int i=1; i<=maxi; i++)
  80. 	{
  81. 		int p=get(vt[i]);
  82. 		if (p!=0) s.insert(p);
  83. 		//cout << i << ' ' << get(vt[i]) << '\n';
  84. 	}
  85. 	cout << s.size() << '\n';
  86. }
  87. int main()
  88. {
  89. 	ios_base::sync_with_stdio(0);
  90. 	//freopen("POSTERS.INP","r",stdin);
  91. 	//freopen("POSTERS.OUT","w",stdout);
  92. 	int t;
  93. 	cin >> t;
  94. 	for (int i=1; i<=t; i++)
  95. 	{
  96. 		enter();
  97. 		solve();
  98. 	}
  99. 	return 0;
  100. }
Success #stdin #stdout 0s 50760KB
comments (?)
stdin
copy 
1
5
1 4
2 6
8 10
3 4
7 10
stdout
copy 
4
https://ideone.com/cYKALM
language:
C++14 (gcc 8.3)
created:
8 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!