fork(1) download
  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
stdin
Standard input is empty
stdout
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