Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的线段树超时了.请好心人帮忙看看.有程序.

Posted by daringQQ at 2006-01-16 10:55:07 on Problem 1803
// 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator