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