fork(1) download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<algorithm>
  5. #include<sstream>
  6. #include<string>
  7. #include<string.h>
  8. #include<deque>
  9. #include<vector>
  10. #include<stack>
  11. #include<queue>
  12. #include<math.h>
  13. #include<map>
  14. #include<set>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long LL;
  19. typedef pair<int,int> pii;
  20.  
  21. double PI = acos(-1);
  22. double EPS = 1e-7;
  23. int INF = 1000000000;
  24. int MAXINT = 2147483647;
  25. LL INFLL = 1000000000000000000LL;
  26. LL MAXLL = 9223372036854775807LL;
  27.  
  28. #define fi first
  29. #define se second
  30. #define mp make_pair
  31. #define pb push_back
  32.  
  33. #define SIZE(a) (int)a.size()
  34. #define ALL(a) a.begin(),a.end()
  35. #define RESET(a,b) memset(a,b,sizeof(a))
  36. #define FOR(a,b,c) for (int (a)=(b); (a)<=(c); (a)++)
  37. #define FORD(a,b,c) for (int (a)=(b); (a)>=(c); (a)--)
  38. #define FORIT(a,b) for (__typeof((b).begin()) a=(b).begin(); a!=(b).end(); (a)++)
  39. #define MIN(a, b) (a) = min((a), (b))
  40. #define MAX(a, b) (a) = max((a), (b))
  41. #define PAUSE system("pause")
  42.  
  43. #define input(in) freopen(in,"r",stdin)
  44. #define output(out) freopen(out,"w",stdout)
  45.  
  46. inline void inp(int &num)
  47. {
  48. 	bool neg=0;
  49. 	num=0;
  50. 	char c;
  51. 	while ((c=getchar_unlocked()) && (!isdigit(c) && c!='-'));
  52. 	if (c=='-')
  53. 	{
  54. 		neg=1;
  55. 		c=getchar_unlocked();
  56. 	}
  57. 	do num=num*10+c-'0';
  58. 	while ((c=getchar_unlocked()) && isdigit(c));
  59. 	num*=(neg)?-1:1;
  60. } 
  61.  
  62. /*\   \
  63. \   \*/
  64.  
  65.  
  66.  
  67. vector<pii> ls[400005];
  68. vector<int> rt[400005];
  69. pair<pii,int> p[100005];
  70.  
  71. vector<pii> loc[100005];
  72.  
  73. inline void merge(int id,vector<pii> &res,vector<pii> &a,vector<pii> &b)
  74. {
  75. 	int la = 0;
  76. 	int lb = 0;
  77. 	int sa = SIZE(a);
  78. 	int sb = SIZE(b);
  79. 	while(la < sa || lb < sb)
  80. 	{
  81. 		if (la >= sa) {res.pb(b[lb]);loc[b[lb].se].pb(mp(id,SIZE(res)-1));lb++;}
  82. 		else if (lb >= sb) {res.pb(a[la]);loc[a[la].se].pb(mp(id,SIZE(res)-1));la++;}
  83. 		else
  84. 		{
  85. 			if (a[la] < b[lb]) {res.pb(a[la]);loc[a[la].se].pb(mp(id,SIZE(res)-1));la++;}
  86. 			else {res.pb(b[lb]);loc[b[lb].se].pb(mp(id,SIZE(res)-1));lb++;}
  87. 		}
  88. 	}
  89. }
  90.  
  91.  
  92. inline void build_x(int n,int l,int r)
  93. {
  94. 	if (l == r)
  95. 	{
  96. 		ls[n].clear();
  97. 		ls[n].pb(mp(p[l].fi.se,p[l].se));
  98. 		rt[n].assign(SIZE(ls[n])<<2,0);
  99. 		loc[p[l].se].pb(mp(n,0));
  100. 		return;
  101. 	}
  102. 	int m = (l+r)>>1;
  103. 	build_x((n<<1),l,m);
  104. 	build_x((n<<1)+1,m+1,r);
  105. 	ls[n].clear();
  106. 	merge(n,ls[n],ls[(n<<1)],ls[(n<<1)+1]);
  107. 	rt[n].assign(SIZE(ls[n])<<2,0);
  108. }
  109.  
  110. inline int query_y(int nx,int n,int l,int r,int ly,int ry)
  111. {
  112. 	if (ly > ls[nx][r].fi || ry < ls[nx][l].fi) return 0;
  113. 	if (ly <= ls[nx][l].fi && ls[nx][r].fi <= ry)
  114. 	{
  115. 		return rt[nx][n];
  116. 	}
  117. 	int res = 0;
  118. 	int m = (l+r)>>1;
  119. 	if (ly <= ls[nx][m].fi) MAX(res,query_y(nx,(n<<1),l,m,ly,min(ls[nx][m].fi,ry)));
  120. 	if (ls[nx][m+1].fi <= ry) MAX(res,query_y(nx,(n<<1)+1,m+1,r,max(ls[nx][m+1].fi,ly),ry));
  121. 	return res;
  122. }
  123.  
  124.  
  125. inline int query_x(int n,int l,int r,int lx,int rx,int ly,int ry)
  126. {
  127. 	if (lx > p[r].fi.fi || rx < p[l].fi.fi) return 0;
  128. 	if (lx <= p[l].fi.fi && p[r].fi.fi <= rx)
  129. 	{
  130. 		return query_y(n,1,0,SIZE(ls[n])-1,ly,ry);
  131. 	}
  132. 	int res = 0;
  133. 	int m = (l+r)>>1;
  134. 	if (lx <= p[m].fi.fi) MAX(res,query_x((n<<1),l,m,lx,min(p[m].fi.fi,rx),ly,ry));
  135. 	if (p[m+1].fi.fi <= rx) MAX(res,query_x((n<<1)+1,m+1,r,max(p[m+1].fi.fi,lx),rx,ly,ry));
  136. 	return res;
  137. }
  138.  
  139.  
  140. inline void update_y(int nx,int n,int l,int r,int fy,int v)
  141. {
  142. 	if (l == r)
  143. 	{
  144. 		MAX(rt[nx][n],v);
  145. 		return;
  146. 	}
  147. 	int m = (l+r)>>1;
  148. 	if (fy <= m) update_y(nx,(n<<1),l,m,fy,v);
  149. 	else update_y(nx,(n<<1)+1,m+1,r,fy,v);
  150. 	rt[nx][n] = max(rt[nx][(n<<1)],rt[nx][(n<<1)+1]);
  151. }
  152.  
  153. int main()
  154. {
  155. 	int t;
  156. 	t=10;
  157. 	FOR(tc,1,t)
  158. 	{
  159. 		int n;
  160. 		n = 100000;
  161. 		pair<pair<pii,pii>,int> d[100005];
  162. 		FOR(a,1,n)
  163. 		{
  164. 			d[a].fi.se.fi= 1;
  165. 			d[a].fi.se.se= 1000000;
  166. 			d[a].fi.fi.fi= 1000000-a;
  167. 			d[a].fi.fi.se= 100;
  168.  
  169. 			loc[a].clear();
  170. 			d[a].se = a;
  171. 			p[a-1] = mp(mp(d[a].fi.se.fi+d[a].fi.se.se,d[a].fi.se.fi-d[a].fi.se.se),a);
  172. 		}
  173.  
  174. 		sort(p,p+n);
  175. 		sort(d+1,d+n+1);
  176.  
  177. 		build_x(1,0,n-1);
  178.  
  179.  
  180. 		int ans = 0;
  181. 		FOR(a,1,n)
  182. 		{
  183. 			int w = d[a].fi.fi.se;
  184. 			int x = d[a].fi.se.fi;
  185. 			int y = d[a].fi.se.se;
  186. 			int id = d[a].se;
  187. 			int val = query_x(1,0,n-1,x+y-w,x+y+w,x-y-w,x-y+w);
  188. 			FOR(b,0,SIZE(loc[id])-1)
  189. 			{
  190. 				update_y(loc[id][b].fi,1,0,SIZE(ls[loc[id][b].fi])-1,loc[id][b].se,val+1);
  191. 			}
  192. 			MAX(ans,val+1);
  193. 		}
  194. 		printf("Case %d: %d\n",tc,ans);
  195. 	}
  196. }
Success #stdin #stdout 3.81s 16600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1: 100000
Case 2: 100000
Case 3: 100000
Case 4: 100000
Case 5: 100000
Case 6: 100000
Case 7: 100000
Case 8: 100000
Case 9: 100000
Case 10: 100000
https://ideone.com/YYpHqv
language:
C++ (gcc 8.3)
created:
12 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!