Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define filer() freopen("in.txt","r",stdin)
- #define filew() freopen("out.txt","w",stdout)
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<math.h>
- #include<algorithm>
- #include<queue>
- #include<stack>
- #include<string>
- #include<vector>
- #include <map>
- #define INF 1<<29
- #define PI pair<int,int>
- #define f first
- #define s second
- #define SET(a, x) memset((a), (x), sizeof(a))
- #define pb push_back
- #define i64 long long
- #define EPS (1e-9)
- using namespace std;
- typedef vector<int> VI;
- typedef vector<PI> vii;
- //i64 INF=(i64)((i64)1<<(i64)59);
- int N;
- struct node
- {
- i64 x;
- i64 y1;
- i64 y2;
- bool t;
- i64 y11;
- i64 y22;
- }A[60009];
- struct point
- {
- int y;
- int ind1;
- int ind2;
- bool t;
- }C[60009];
- i64 B[30009];
- bool cmp(point a,point b)
- {
- return a.y<b.y;
- }
- bool cmp1(node a,node b)
- {
- return a.x<b.x;
- }
- i64 M[262150],L[262150],total[262150];
- void init(int b,int e,int i)
- {
- if(b==e)
- {
- M[i]=B[b];
- total[i]=B[b];
- }
- else
- {
- int mid=(b+e)/2;
- init(b,mid,2*i);
- init(mid+1,e,2*i+1);
- M[i]=M[2*i]+M[2*i+1];
- total[i]=total[2*i]+total[2*i+1];
- }
- }
- void update(int b,int e,int lo,int hi,int i,int val)
- {
- if(b>hi || e<lo)return;
- if(lo<=b && e<=hi)
- {
- L[i]+=val;
- if(L[i])M[i]=0;
- else if(b!=e)M[i]=M[2*i]+M[2*i+1];
- else M[i]=B[b];
- return;
- }
- /*if(L[i]){
- L[2*i]+=L[i];
- L[2*i+1]+=L[i];
- L[i]=0;
- if(L[2*i])M[2*i]=0;
- else M[2*i]=total[2*i];
- if(L[2*i+1])M[2*i+1]=0;
- else M[2*i+1]=total[2*i+1];}*/
- int mid=(b+e)/2;
- update(b,mid,lo,hi,2*i,val);
- update(mid+1,e,lo,hi,2*i+1,val);
- if(L[i])M[i]=0;
- else M[i]=M[2*i]+M[2*i+1];
- }
- i64 query(int b,int e,int lo,int hi,int i)
- {
- if(b>hi || e<lo)return -1;
- if(lo<=b && e<=hi)
- {
- return M[i];
- }
- if(L[i]){
- L[2*i]+=L[i];
- L[2*i+1]+=L[i];
- L[i]=0;
- if(L[2*i])M[2*i]=0;
- else M[2*i]=total[2*i];
- if(L[2*i+1])M[2*i+1]=0;
- else M[2*i+1]=total[2*i+1];}
- int mid=(b+e)/2;
- i64 p1=query(b,mid,lo,hi,2*i);
- i64 p2=query(mid+1,hi,lo,hi,2*i+1);
- M[i]=M[2*i]+M[2*i+1];
- if(p1==-1)return p2;
- else if(p2==-1)return p1;
- return p1+p2;
- }
- int main()
- {
- //filer();
- int T,cas=0;
- int i,j,x1,y1,x2,y2;
- scanf("%d",&T);
- while(T--)
- {
- SET(M,0);
- SET(L,0);
- SET(total,0);
- scanf("%d",&N);
- for(i=0;i<N;i++)
- {
- scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
- A[2*i].x=x1;
- A[2*i].y1=y1;
- A[2*i].y2=y2;
- A[2*i].t=0;
- A[2*i+1].x=x2;
- A[2*i+1].y1=y1;
- A[2*i+1].y2=y2;
- A[2*i+1].t=1;
- C[2*i].y=y1;
- C[2*i].ind1=2*i;
- C[2*i].ind2=2*i+1;
- C[2*i].t=0;
- C[2*i+1].y=y2;
- C[2*i+1].ind1=2*i;
- C[2*i+1].ind2=2*i+1;
- C[2*i+1].t=1;
- }
- sort(C,C+2*N,cmp);
- int k=1;
- B[0]=C[0].y;
- if(C[0].t)
- {
- A[C[0].ind1].y22=k;
- A[C[0].ind2].y22=k;
- }
- else
- {
- A[C[0].ind1].y11=k;
- A[C[0].ind2].y11=k;
- }
- for(i=1;i<2*N;i++)
- {
- if(C[i].y!=C[i-1].y)
- {
- k++;
- B[k-1]=C[i].y-C[i-1].y;
- }
- if(C[i].t)
- {
- A[C[i].ind1].y22=k;
- A[C[i].ind2].y22=k;
- }
- else
- {
- A[C[i].ind1].y11=k;
- A[C[i].ind2].y11=k;
- }
- }
- sort(A,A+2*N,cmp1);
- //for(i=0;i<k;i++)cout<<B[i]<<' ';cout<<endl;
- //cout<<"x y11 y22 t"<<endl;;
- //for(i=0;i<2*N;i++)cout<<A[i].x<<' '<<A[i].y11<<' '<<A[i].y22<<' '<<A[i].t<<endl;
- init(0,k-1,1);
- //cout<<M[1]<<endl;
- int x=0;
- i64 q,ans=0;
- for(i=0;i<2*N;i++)
- {
- //q=query(0,k-1,A[i].y11,A[i].y22-1,1);
- ans+=((A[i].x-x)*(total[1]-M[1]));
- if(A[i].t)update(0,k-1,A[i].y11,A[i].y22-1,1,-1);
- else update(0,k-1,A[i].y11,A[i].y22-1,1,1);
- x=A[i].x;
- }
- //cout<<ans<<endl;
- printf("Case %d: %lld\n",++cas,ans);
- }
- return 0;
- }
- /*
- Test Case:
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement