fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #define MAX 10000000+100
  5. typedef long long int ll;
  6. using namespace std;
  7. ll Tree[3*MAX],lazy[MAX*2];
  8.  
  9.  
  10. void Update(ll s,ll start,ll end,ll left,ll right,ll value)
  11. {
  12. 	if(lazy[s]!=0)
  13. 	{
  14. 		Tree[s]=(lazy[s]*(end-start+1));
  15. 		if(start!=end)lazy[2*s+1]=lazy[s],lazy[s*2+2]=lazy[s];
  16. 		lazy[s]=0;
  17. 	}
  18. 	if(start>end||left>end||right<start)return;
  19. 	if(start>=left&&end<=right)
  20. 	{
  21. 		Tree[s] = (value*(end-start+1));
  22. 		if(start!=end)
  23. 		{
  24. 			lazy[2*s+1]=value;
  25. 			lazy[2*s+2]=value;
  26. 		}
  27. 		return ;
  28. 	}
  29. 	ll mid=(start+end)/2;
  30. 	Update(2*s+1,start,mid,left,right,value);
  31. 	Update(2*s+2,mid+1,end,left,right,value);
  32. 	Tree[s] = Tree[s*2+1]+Tree[2*s+2];
  33. }
  34.  
  35. ll Read(ll s,ll start,ll end,ll left,ll right)
  36. {
  37. 	if(start>end||start>right||end<left)return 0;
  38. 	if(lazy[s]!=0)
  39. 	{
  40. 		Tree[s]=(lazy[s]*(end-start+1));
  41. 		if(start!=end)
  42. 		{
  43. 			lazy[2*s+1]=lazy[s];
  44. 			lazy[2*s+2]=lazy[s];
  45. 		}
  46. 		lazy[s]=0;
  47. 	}
  48. 	if(start>=left&&end<=right)return Tree[s];
  49. 	else return (Read(2*s+1,start,(start+end)/2,left,right)+Read(2*s+2,1+((start+end)/2),end,left,right));
  50.  
  51. }
  52. int main() {
  53. 	// your code goes here
  54. 	ll t;
  55. 	cin>>t;
  56. 	while(t--)
  57. 	{
  58. 		ll n,z=1,li=-1;
  59. 		cin>>n;
  60. 		vector<pair<ll,ll> > b;
  61. 		for(ll i=0;i<n;i++)
  62. 		{
  63. 			ll u,v;
  64. 			li = max(li,v);
  65. 			cin>>u>>v;
  66. 			b.push_back(make_pair(u-1,v-1));
  67. 		}
  68. 		for(auto v: b)
  69. 			Update(0,0,li+2,v.first,v.second,z++);
  70. 		set<ll> a;
  71.  
  72. 		for(ll i=0;i<li+2;i++)cout<<Read(0,0,li+2,i,i)<<" ",a.insert(Read(0,0,li+2,i,i));
  73. 		cout<<endl;
  74. 		cout<<a.size()-1<<endl;
  75. 	}
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 315968KB
comments ()
stdin
copy 
2
5
1 4
2 6
8 10
3 4
7 10
5
1 4
2 6
6 10
3 4
7 10
stdout
copy 
1 2 4 4 2 2 5 5 5 5 0 0 
4
1 2 4 4 2 3 5 5 5 5 0 0 
5
https://ideone.com/gBJKnL
language:
C++14 (gcc 8.3)
created:
9 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!