Advertisement
farsid

Untitled

Mar 18th, 2013
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.46 KB | None | 0 0
  1. #define filer() freopen("in.txt","r",stdin)
  2. #define filew() freopen("out.txt","w",stdout)
  3. #include<iostream>
  4. #include<stdio.h>
  5. #include<string.h>
  6. #include<math.h>
  7. #include<algorithm>
  8. #include<queue>
  9. #include<stack>
  10. #include<string>
  11. #include<vector>
  12. #include <map>
  13. #define INF 1<<29
  14. #define PI pair<int,int>
  15. #define f first
  16. #define s second
  17. #define SET(a, x) memset((a), (x), sizeof(a))
  18. #define pb push_back
  19. #define i64 long long
  20. #define EPS (1e-9)
  21. using namespace std;
  22. typedef vector<int> VI;
  23. typedef vector<PI> vii;
  24. //i64 INF=(i64)((i64)1<<(i64)59);
  25.  
  26. int N;
  27.  
  28. struct node
  29. {
  30. i64 x;
  31. i64 y1;
  32. i64 y2;
  33. bool t;
  34. i64 y11;
  35. i64 y22;
  36. }A[60009];
  37.  
  38. struct point
  39. {
  40. int y;
  41. int ind1;
  42. int ind2;
  43. bool t;
  44. }C[60009];
  45.  
  46. i64 B[30009];
  47.  
  48. bool cmp(point a,point b)
  49. {
  50. return a.y<b.y;
  51. }
  52.  
  53. bool cmp1(node a,node b)
  54. {
  55. return a.x<b.x;
  56. }
  57. i64 M[262150],L[262150],total[262150];
  58. void init(int b,int e,int i)
  59. {
  60. if(b==e)
  61. {
  62. M[i]=B[b];
  63. total[i]=B[b];
  64. }
  65. else
  66. {
  67. int mid=(b+e)/2;
  68. init(b,mid,2*i);
  69. init(mid+1,e,2*i+1);
  70. M[i]=M[2*i]+M[2*i+1];
  71. total[i]=total[2*i]+total[2*i+1];
  72. }
  73. }
  74.  
  75. void update(int b,int e,int lo,int hi,int i,int val)
  76. {
  77. if(b>hi || e<lo)return;
  78.  
  79. if(lo<=b && e<=hi)
  80. {
  81. L[i]+=val;
  82. if(L[i])M[i]=0;
  83. else if(b!=e)M[i]=M[2*i]+M[2*i+1];
  84. else M[i]=B[b];
  85. return;
  86. }
  87. /*if(L[i]){
  88. L[2*i]+=L[i];
  89. L[2*i+1]+=L[i];
  90. L[i]=0;
  91. if(L[2*i])M[2*i]=0;
  92. else M[2*i]=total[2*i];
  93. if(L[2*i+1])M[2*i+1]=0;
  94. else M[2*i+1]=total[2*i+1];}*/
  95.  
  96. int mid=(b+e)/2;
  97. update(b,mid,lo,hi,2*i,val);
  98. update(mid+1,e,lo,hi,2*i+1,val);
  99. if(L[i])M[i]=0;
  100. else M[i]=M[2*i]+M[2*i+1];
  101. }
  102.  
  103. i64 query(int b,int e,int lo,int hi,int i)
  104. {
  105. if(b>hi || e<lo)return -1;
  106.  
  107. if(lo<=b && e<=hi)
  108. {
  109. return M[i];
  110. }
  111. if(L[i]){
  112. L[2*i]+=L[i];
  113. L[2*i+1]+=L[i];
  114. L[i]=0;
  115. if(L[2*i])M[2*i]=0;
  116. else M[2*i]=total[2*i];
  117. if(L[2*i+1])M[2*i+1]=0;
  118. else M[2*i+1]=total[2*i+1];}
  119.  
  120. int mid=(b+e)/2;
  121. i64 p1=query(b,mid,lo,hi,2*i);
  122. i64 p2=query(mid+1,hi,lo,hi,2*i+1);
  123.  
  124. M[i]=M[2*i]+M[2*i+1];
  125. if(p1==-1)return p2;
  126. else if(p2==-1)return p1;
  127. return p1+p2;
  128. }
  129.  
  130. int main()
  131. {
  132. //filer();
  133. int T,cas=0;
  134. int i,j,x1,y1,x2,y2;
  135. scanf("%d",&T);
  136. while(T--)
  137. {
  138. SET(M,0);
  139. SET(L,0);
  140. SET(total,0);
  141. scanf("%d",&N);
  142. for(i=0;i<N;i++)
  143. {
  144. scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  145. A[2*i].x=x1;
  146. A[2*i].y1=y1;
  147. A[2*i].y2=y2;
  148. A[2*i].t=0;
  149. A[2*i+1].x=x2;
  150. A[2*i+1].y1=y1;
  151. A[2*i+1].y2=y2;
  152. A[2*i+1].t=1;
  153. C[2*i].y=y1;
  154. C[2*i].ind1=2*i;
  155. C[2*i].ind2=2*i+1;
  156. C[2*i].t=0;
  157. C[2*i+1].y=y2;
  158. C[2*i+1].ind1=2*i;
  159. C[2*i+1].ind2=2*i+1;
  160. C[2*i+1].t=1;
  161. }
  162. sort(C,C+2*N,cmp);
  163. int k=1;
  164. B[0]=C[0].y;
  165. if(C[0].t)
  166. {
  167. A[C[0].ind1].y22=k;
  168. A[C[0].ind2].y22=k;
  169. }
  170. else
  171. {
  172. A[C[0].ind1].y11=k;
  173. A[C[0].ind2].y11=k;
  174. }
  175. for(i=1;i<2*N;i++)
  176. {
  177. if(C[i].y!=C[i-1].y)
  178. {
  179. k++;
  180. B[k-1]=C[i].y-C[i-1].y;
  181. }
  182. if(C[i].t)
  183. {
  184. A[C[i].ind1].y22=k;
  185. A[C[i].ind2].y22=k;
  186. }
  187. else
  188. {
  189. A[C[i].ind1].y11=k;
  190. A[C[i].ind2].y11=k;
  191. }
  192.  
  193. }
  194. sort(A,A+2*N,cmp1);
  195. //for(i=0;i<k;i++)cout<<B[i]<<' ';cout<<endl;
  196. //cout<<"x y11 y22 t"<<endl;;
  197. //for(i=0;i<2*N;i++)cout<<A[i].x<<' '<<A[i].y11<<' '<<A[i].y22<<' '<<A[i].t<<endl;
  198. init(0,k-1,1);
  199. //cout<<M[1]<<endl;
  200.  
  201. int x=0;
  202. i64 q,ans=0;
  203. for(i=0;i<2*N;i++)
  204. {
  205. //q=query(0,k-1,A[i].y11,A[i].y22-1,1);
  206. ans+=((A[i].x-x)*(total[1]-M[1]));
  207. if(A[i].t)update(0,k-1,A[i].y11,A[i].y22-1,1,-1);
  208. else update(0,k-1,A[i].y11,A[i].y22-1,1,1);
  209. x=A[i].x;
  210. }
  211. //cout<<ans<<endl;
  212. printf("Case %d: %lld\n",++cas,ans);
  213. }
  214.  
  215. return 0;
  216. }
  217. /*
  218. Test Case:
  219.  
  220. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement