| ||||||||||
| 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