Poj Solution 1803

http://poj.org/problem?id=1803

#include"stdio.h"
#include<iostream>
#include"memory.h"
#include"algorithm"

using namespace std;

int tree[1024*1024*2];
int stop[1024*1024*2];
long m[1024*1024*2];
long area;
int x1,y1,x2,y2,key;
long temp;
void search(int s,long mj);

void find(int xu,int yu,int xd,int yd,long s,long mj,int k)
{
 if(xu>=x2||xd<=x1||yu>=y2||yd<=y1){return;}
 
 if(key){tree[s]++;}
 if(!key){tree[s]--;}
 
 if(xu>=x1&&yu>=y1&&xd<=x2&&yd<=y2)
 {if(!key)stop[s]--;else tree[s]--;
    if(!k){temp=0;//search(s,mj);
           if(key)area+=mj-temp;
           else area-=mj-temp;
            }
  if(key){stop[s]++;tree[s]++;m[s]=mj;}
  else if(!stop[s]){if(mj==1)m[s]=0;else m[s]=m[s*4+1]+m[s*4+2]+m[s*4+3]+m[s*4+4];}
  return;}
//if(xd-xu<=1&&yd-yu<=1)return;
 if(stop[s])k=1;
 
 find(xu,yu,(xu+xd)/2,(yu+yd)/2,s*4+1,mj/4,k);
 find((xu+xd)/2,yu,xd,(yu+yd)/2,s*4+2,mj/4,k);
 find(xu,(yu+yd)/2,(xu+xd)/2,yd,s*4+3,mj/4,k);
 find((xu+xd)/2,(yu+yd)/2,xd,yd,s*4+4,mj/4,k);
 if(!stop[s])m[s]=m[s*4+1]+m[s*4+2]+m[s*4+3]+m[s*4+4];
}


int index[4000];
int x[4000],y[4000],xx[4000],yy[4000],z[4000],n;int sign[4000];
int xb,yb,zb,xe,ye,ze;

////////////////////////////////////////////
int cmp(int a,int b)
{return z[a]<z[b];}

void init()
{int i,x1,y1,z1,x2,y2,z2,h;
//cin>>xb>>yb>>zb>>xe>>ye>>ze;
scanf("%d%d%d%d%d%d",&xb,&yb,&zb,&xe,&ye,&ze);
n=0;
//cin>>h;
scanf("%d",&h);
for(i=0;i<h;i++)
{//cin>>x1>>y1>>z1>>x2>>y2>>z2;
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
if(x1<xb)x1=xb;
if(y1<yb)y1=yb;
if(z1<zb)z1=zb;

if(x2>xe)x2=xe;
if(y2>ye)y2=ye;
if(z2>ze)z2=ze;

if(x2>x1&&y2>y1&&z2>z1)
{x[n]=x1;y[n]=y1;xx[n]=x2;yy[n]=y2;z[n]=z1;sign[n]=1;index[n]=n;n++;
 x[n]=x1;y[n]=y1;xx[n]=x2;yy[n]=y2;z[n]=z2;sign[n]=0;index[n]=n;n++;
}

}

sort(&index[0],&index[n],cmp);
area=0;
memset(tree,0,1024*1024*2*sizeof(int));
memset(stop,0,1024*1024*2*sizeof(int));
memset(m,0,1024*1024*2*sizeof(long));
}
long v;
///////////////////////////
void doit()
{int i;v=0;

for(i=0;i<n;i++)
{x1=x[index[i]];x2=xx[index[i]];
 y1=y[index[i]];y2=yy[index[i]];
 key=sign[index[i]];
 find(0,0,1024,1024,0,1024*1024,0);
 area=m[0];
 //search(0,1024*1024);
 if(i<n-1)v+=area*(z[index[i+1]]-z[index[i]]);
}

}

int main()
{int t,i;
//cin>>t;
scanf("%d",&t);
for(i=1;i<=t;i++)
{cout<<"Scenario #"<<i<<":"<<endl;
 init();
 doit();
 cout<<v<<endl<<endl;
}

return 0;
}