fork download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<stack>
  7. #include<set>
  8. #include<queue>
  9. #include<string>
  10. #include<iostream>
  11. #include<map>
  12. #include<cstdlib>
  13. #include<ctime> 
  14. using namespace std;
  15.  
  16. //freopen("in.txt","r",stdin);	FILE-IO 
  17. //fclose(stdin);		FILE-IO
  18. //srand (time(NULL));		RANDOM NUMBERS
  19.  
  20. #define M_PI 3.14159265358979323846 /* pi */
  21. #define _USE_MATH_DEFINES
  22. #define db(a) printf("check%d\n",(a))
  23. #define dbg(a,b) printf("check%d %d\n",(a),(b))
  24. #define sd(a) scanf("%d",&a)
  25. #define pd(a) prlong longf("%lld\n",(a))
  26. #define clr(a) memset(a,0,sizeof(a))
  27. #define LL long long
  28. #define F first
  29. #define S second
  30. #define MP make_pair
  31. #define PB push_back
  32. #define LIM 200000
  33. set<int> s[LIM];
  34. map<int,int> comp1;
  35. map<int,int> comp[LIM];
  36. vector<int> bit[LIM];
  37. pair<int,int> a[LIM];
  38. pair<int,int> a1[LIM];
  39. set<int> temp;
  40. int cnt1;
  41. int cnt[LIM];
  42. int query1(int i,int idx)
  43. {
  44. 	int ret=0;
  45. 	while(idx)
  46. 	{
  47. 		ret=max(ret,bit[i][idx]);
  48. 		idx=idx-(idx&(-idx));
  49. 	}
  50. 	return ret;
  51. }
  52. int query(int idx,int val)
  53. {
  54. 	int ret=0;
  55. 	while(idx)
  56. 	{
  57. 		map<int,int>::iterator it=comp[idx].lower_bound(val);
  58. 		int pos;
  59. 		if(it==comp[idx].end())
  60. 			pos=cnt[idx];
  61. 		else
  62. 			pos=(*it).S-1;	
  63. 		//int pos=(*(comp[idx].lower_bound(val))).S;
  64. 		//if(pos==0)
  65. 		//	pos=cnt[idx];
  66. 		//else
  67. 		//	--pos;
  68. 		ret=max(ret,query1(idx,pos));
  69. 		idx=idx-(idx&(-idx));
  70. 	}
  71. 	return ret;
  72. }
  73. void update1(int i,int idx,int val)
  74. {
  75. 	while(idx<=cnt[i])
  76. 	{
  77. 		bit[i][idx]=max(bit[i][idx],val);
  78. 		idx=idx+(idx&(-idx));
  79. 	}
  80. }
  81. void update(int val1,int idx,int val)
  82. {
  83. 	while(idx<=cnt1)
  84. 	{
  85. 		//db(11);
  86. 		int pos=comp[idx][val];
  87. 		//dbg(val,pos);
  88. 		update1(idx,pos,val1);
  89. 		idx=idx+(idx&(-idx)); 
  90. 	}
  91. }
  92. int main()
  93. {
  94. 	//freopen("in.txt","r",stdin);
  95. 	//freopen("out.txt","w",stdout);
  96. 	int n,i,j,k,x,y,ans=0;
  97. 	cnt1=0;
  98. 	//db(1);
  99. 	for(i=0;i<LIM;++i)
  100. 		cnt[i]=0;
  101. 	//db(2);
  102. 	sd(n);
  103. 	for(i=0;i<n;++i)
  104. 	{
  105. 		//db(3);
  106. 		sd(x);
  107. 		sd(y);
  108. 		a[i]=MP(x,y);
  109. 		a1[i]=MP(x,y);
  110. 	}
  111. 	sort(a1,a1+n);
  112. 	for(i=0;i<n;++i)
  113. 	{
  114. 		if(!comp1[a1[i].F])
  115. 			comp1[a1[i].F]=++cnt1;
  116. 		s[comp1[a1[i].F]].insert(a1[i].S);
  117. 	}
  118.  
  119. 	//db(4);
  120. 	for(i=1;i<=cnt1;++i)
  121. 	{
  122. 		//db(5);
  123. 		temp.clear();
  124. 		for(j=i;j>(i-(i&(-i)));--j)
  125. 		{
  126. 			//db(6);
  127.  
  128. 			set<int>::iterator it=s[j].begin();
  129. 			for(;it!=s[j].end();++it)
  130. 			{
  131. 				//db(7);
  132. 				//int val=*it;
  133. 				temp.insert(*it);
  134. 				//if(!comp[i][val])
  135. 				//{
  136. 				//	comp[i][val]=++cnt[i];
  137. 				//}
  138. 			}
  139. 		}
  140. 		set<int>::iterator it=temp.begin();
  141. 		for(;it!=temp.end();++it)
  142. 		{
  143. 			comp[i][*it]=++cnt[i];
  144. 		}
  145. 		bit[i].resize(cnt[i]+1,0);
  146. 	}
  147.  
  148. 	for(i=0;i<n;++i)
  149. 	{
  150. 		int ans1=1+query(comp1[a[i].F]-1,a[i].S);
  151. 		ans=max(ans,ans1);
  152. 		update(ans1,comp1[a[i].F],a[i].S);
  153. 	}
  154. 	//for(i=0;i<n;++i)
  155. 	//{
  156. 	//	printf("%d %d\n",a1[i].F,comp1[a1[i].F]);	
  157. 	//}
  158. 	printf("%d",ans);
  159. }
Success #stdin #stdout 0.01s 18456KB
comments (?)
stdin
copy 
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6
stdout
copy 
3
https://ideone.com/kaYVz1
language:
C++ 4.3.2 (gcc-4.3.2)
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!