Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我的线段树超时了.请好心人帮忙看看.有程序.// pk1803.cpp : Defines the entry point for the console application. // #include <cstdio> #include <algorithm> using namespace std; struct Node{ short left,right; short count; Node *lcd,*rcd; void Build(int,int); void Insert(int,int); void Delete(int,int); int GetM(); }node[2000],*root=&node[0]; struct Data{ short x,y1,y2,z1,z2; bool left; }line[4000]; int yy[4000],zz[4000]; int up; void Node::Build(int l,int r){ left=l; right=r; count=0; if(r-l>1){ int mid=(l+r)/2; lcd=&node[++up]; lcd->Build(l,mid); rcd=&node[++up]; rcd->Build(mid,r); } else{ lcd=NULL; rcd=NULL; } } void Node::Insert(int l,int r){ if(l<=yy[left] && r>=yy[right]){ count++; return; } if(l<yy[lcd->right]) lcd->Insert(l,r); if(r>yy[rcd->left]) rcd->Insert(l,r); } void Node::Delete(int l,int r){ if(l<=yy[left] && r>=yy[right]){ count--; return; } if(l<yy[lcd->right]) lcd->Delete(l,r); if(r>yy[rcd->left]) rcd->Delete(l,r); } int Node::GetM(){ if(count>0) return yy[right]-yy[left]; if(left+1==right) return 0; return lcd->GetM()+rcd->GetM(); } bool operator < (const Data &a,const Data &b){ return a.x<b.x; } int main(int argc, char* argv[]) { int cases,t,n,i,j,k,x1,y1,z1,x2,y2,z2,maxy,ans,now; scanf("%d",&cases); for(t=1;t<=cases;t++){ scanf("%d %d %d %d %d %d %d",&x1,&y1,&z1,&x2,&y2,&z2,&n); j=0; for(i=0;i<n;i++){ scanf("%d %d %d %d %d %d",&x1,&y1,&z1,&x2,&y2,&z2); line[j].x=x1;line[j].y1=y1;line[j].y2=y2;line[j].z1=z1;line[j].z2=z2;line[j].left=1; yy[j]=y1;zz[j++]=z1; line[j].x=x2;line[j].y1=y1;line[j].y2=y2;line[j].z1=z1;line[j].z2=z2;line[j].left=0; yy[j]=y2;zz[j++]=z2; } n*=2; sort(line,line+n); sort(yy,yy+n); sort(zz,zz+n); j=1; for(i=1;i<n;i++) if(yy[i]!=yy[i-1]) yy[j++]=yy[i]; maxy=j-1; j=1; for(i=1;i<n;i++) if(zz[i]!=zz[i-1]) zz[j++]=zz[i]; ans=0; now=0; up=0; root->Build(0,maxy); for(k=0;k<j-1;k++) for(i=0;i<n;i++) if(line[i].z1<=zz[k] && line[i].z2>=zz[k+1]){ ans+=(line[i].x-now)*root->GetM()*(zz[k+1]-zz[k]); now=line[i].x; if(line[i].left) root->Insert(line[i].y1,line[i].y2); else root->Delete(line[i].y1,line[i].y2); } printf("Scenario #%d:\n",t); printf("%d\n\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator