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

离散处理后的版本,也tle了

Posted by hudedi at 2006-07-17 01:36:50 on Problem 2777
In Reply To:我用的线段树,为什么会tle啊 Posted by:hudedi at 2006-07-17 01:35:30
> my code,please help me
> /*pku 2777*/
> #include<stdio.h>
> #define N 100005
> struct TREE	
> {
> 	int color,l,r,mid;
> }tree[N*4+1000];
> int l,t,o;
> int a,b,d;
> 
> void creat(int s,int e,int p)
> {
> 	int mid;
> 	mid=(s+e)>>1;
> 	tree[p].l=s,tree[p].r=e;
> 	tree[p].mid=mid;
> 	tree[p].color=1;
> 	if(s==e)
> 		return;
> 	
> 	creat(s,mid,p*2);
> 	creat(mid+1,e,p*2+1);
> }
> 
> void insert(int s,int e,int c,int p)
> {
> 	if(tree[p].r==tree[p].l)/*******/
> 	{
> 		tree[p].color=1<<(c-1);/**********/
> 		  return;
> 	}
> 	if(e<=tree[p].mid)
> 		insert(s,e,c,p*2);
> 	else if(s>tree[p].mid)
> 		insert(s,e,c,p*2+1);
> 	else 
> 	{
> 		insert(s,tree[p].mid,c,p*2);
> 		insert(tree[p].mid+1,e,c,p*2+1);
> 	}
> 	tree[p].color=tree[p*2].color|tree[p*2+1].color;
> 	/*if(tree[p*2].color!=1)
> 		printf("fff%d  %d  %d\n",tree[p].color,tree[p*2].color,tree[p*2+1].color);*/
> }
> 
> int get(int s,int e,int p)
> {    
> 		if(s==tree[p].l&&e==tree[p].r)
> 			return tree[p].color;
> 		if(e<=tree[p].mid)
> 			return get(s,e,p*2);
> 		else if(s>tree[p].mid)
> 			return get(s,e,p*2+1);
> 		else 
> 			return get(s,tree[p].mid,p*2)|get(tree[p].mid+1,e,p*2+1);		
> }
> 
> void change()
> {
> 	int temp;
> 	temp=a;
> 	a=b;
> 	b=temp;	
> }
> 
> int main()
> {
> 	char s[3];
> 	int ii;
> 	int temp,time;
> 	while(scanf("%d %d %d",&l,&t,&o)!=EOF)
> 	{
> 		creat(1,l,1);
> 		for(ii=0;ii<o;ii++)
> 		{
> 			scanf("%s",s);
> 			switch(s[0])
> 			{
> 				case 'C':scanf("%d %d %d",&a,&b,&d);
> 								if(a>b)
> 									change();
> 								insert(a,b,d,1);
> 								 
> 								 break;
> 			  case 'P':scanf("%d %d",&a,&b);
> 			  				if(a>b)
> 									change();
> 			  				 temp=get(a,b,1);
> 			  				 /*printf("%d\n",temp);*/
> 			  				 time=0;
> 			  				 while(temp)
> 			  				 {
> 			  				 	if(temp%2)
> 			  				 		time++;
> 			  				 	temp>>=1;
> 			  				 			
> 			  				 }
> 			  				 printf("%d\n",time);
> 			  				 
> 			}
> 		}
> 	}	
> 	return 1;
> }
> /*
> 2 2 4
> C 1 1 2
> P 1 2
> C 2 2 2
> P 1 2
> */
> 
> 

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