fork(5) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. const int MOD	= 1e9 + 7;
  7.  
  8. #define fastio			std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  9. #define test int t;cin>>t;while(t--)
  10.  
  11. double tick(){static clock_t oldt,newt=clock();double diff=1.0*(newt-oldt)/CLOCKS_PER_SEC;oldt=newt;return diff;}
  12.  
  13. namespace patch
  14. {
  15.     template < typename T > std::string to_string( const T& n )
  16.     {
  17.         std::ostringstream stm ;
  18.         stm << n ;
  19.         return stm.str() ;
  20.     }
  21. }
  22.  
  23. int ipow(int b, int e) {
  24.     if (e == 0)
  25.         return 1;
  26.     return e == 0 ? 1 : b * ipow(b, e - 1);
  27. }
  28.  
  29. const int MAX=40005;
  30.  
  31. int segTree[4*MAX],lazyTree[4*MAX];
  32.  
  33. void lazyupd(int loq,int hiq,int lo,int hi,int pos,int val)
  34. {
  35. 	if(lazyTree[pos]!=0)
  36. 	{
  37. 		segTree[pos]=lazyTree[pos];
  38. 		if(lo!=hi)
  39. 		{
  40. 			lazyTree[2*pos]=lazyTree[pos];
  41. 			lazyTree[2*pos+1]=lazyTree[pos];
  42. 		}
  43. 		lazyTree[pos]=0;
  44. 	}
  45.  
  46. 	//if(lo>hi) return;
  47.  
  48. 	if(loq>hi || hiq<lo || lo>hi) return;
  49.  
  50. 	if(loq<=lo && hiq>=hi)
  51. 	{
  52. 		segTree[pos]=val;
  53. 		if(lo!=hi)
  54. 		{
  55. 			lazyTree[2*pos]=val;
  56. 			lazyTree[2*pos+1]=val;
  57. 		}
  58. 		return;
  59. 	}
  60.  
  61. 	int mid=(lo+hi)/2;
  62.  
  63. 	lazyupd(loq,hiq,lo,mid,2*pos,val);
  64. 	lazyupd(loq,hiq,mid+1,hi,2*pos+1,val);
  65.  
  66. 	segTree[pos]=val;
  67.  
  68. }
  69.  
  70. int segQuer(int loq,int hiq,int lo,int hi,int pos)
  71. {
  72. 	if(lazyTree[pos]!=0)
  73. 	{
  74. 		segTree[pos]=lazyTree[pos];
  75.  
  76. 		if(lo!=hi)
  77. 		{
  78. 			lazyTree[2*pos]=lazyTree[pos];
  79. 			lazyTree[2*pos+1]=lazyTree[pos];
  80. 		}
  81. 		lazyTree[pos]=0;
  82. 	}
  83.  
  84. 	if(loq>hi || hiq<lo || lo>hi) return 0;
  85.  
  86. 	if(loq<=lo && hiq>=hi) return segTree[pos];
  87.  
  88. 	int mid=(lo+hi)/2;
  89.  
  90. 	return segQuer(loq,hiq,lo,mid,2*pos)+segQuer(loq,hiq,mid+1,hi,2*pos+1);
  91. }
  92.  
  93. int main() {
  94. 	#ifndef ONLINE_JUDGE
  95. 		freopen("inp.txt", "r", stdin);
  96. 		freopen("output.txt","w", stdout);
  97. 	#endif
  98. 	fastio;
  99.  
  100.  
  101. 	test{
  102. 		memset(segTree,0,sizeof(segTree));
  103. 		memset(lazyTree,0,sizeof(lazyTree));
  104. 		int n;cin>>n;
  105.  
  106. 		pair<int,int> ranges[MAX];
  107. 		vector<int> arr;
  108. 		map<int,int> seen;
  109. 		for(int i=0;i<n;i++)
  110. 		{
  111. 			int l,r;cin>>l>>r;
  112. 			//l--,r--;
  113.  
  114. 			ranges[i].first=l;
  115. 			ranges[i].second=r;
  116.  
  117. 			if(seen[l]==0)
  118. 			{
  119. 				arr.push_back(l);
  120. 				seen[l]=1;
  121. 			}
  122. 			if(seen[r]==0)
  123. 			{
  124. 				arr.push_back(r);
  125. 				seen[r]=1;
  126. 			}	
  127. 		}
  128. 		sort(arr.begin(),arr.end());
  129.  
  130. 		map<int,int> compress;
  131.  
  132. 		for(int i=0;i<arr.size();i++)
  133. 			compress[arr[i]]=i+1;
  134. 		for(int i=0;i<n;i++)
  135. 			lazyupd(compress[ranges[i].first],compress[ranges[i].second],1,arr.size(),1,i+1);
  136.  
  137. 		set<int> res;
  138.  
  139. 		for(int i=1;i<=arr.size();i++)
  140. 		{
  141. 			res.insert(segQuer(i,i,1,arr.size(),1));
  142. 		}
  143.  
  144. 		int result=res.size();
  145.  
  146. 		if(res.find(0)!=res.end())
  147. 			result--;
  148.  
  149. 		cout<<result<<"\n";
  150. 	}
  151.  
  152. 	//cout<<tick()<<"\n";
  153. 	return 0;
  154.  
  155. }
  156.  
Success #stdin #stdout 0s 16672KB
comments (?)
stdin
copy 
1
5
1 4
2 6
8 10
3 4
7 10
stdout
copy 
4
https://ideone.com/w51s0z
language:
C++14 (gcc 8.3)
created:
4 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!