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 |
离散处理后的版本,也tle了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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator