Poj Solution 1823

http://poj.org/problem?id=1823

#include"stdio.h"
#include"memory.h"

const int L=2048*16;
short left[L],right[L],max[L];char stop[L];
#define bigger(a,b) (((a)>(b))?(a):(b))
//inline short bigger(short a,short b)
//{return a>b?a:b;}
short a,b,key;
void insert(short root,short begin,short end)
{
    if(begin>end||b<begin||end<a)return;
    short l1,l2,*l=&left[root],*r=&right[root]; 
    if(a<=begin&&end<=b)
    {
        stop[root]=1;
        if(key==1)
        {
            (*l)=(*r)=max[root]=0;
        }
        
        else 
        {
            (*l)=(*r)=max[root]=end-begin+1;
        }
        return;
    }

    l1=(begin+end)/2-begin+1;
    l2=end-(begin+end)/2;

    short ji=root*2+1,ou=root*2+2;
    if(stop[root])
    {
        stop[root]=0;stop[ji]=1;stop[ou]=1;

        if(max[root]>0)
        {
            left[ji]=right[ji]=max[ji]=l1;
            left[ou]=right[ou]=max[ou]=l2;
        }
        else
        {
            left[ji]=right[ji]=max[ji]=0;
             left[ou]=right[ou]=max[ou]=0;
        }
    }
    insert(ji,begin,(begin+end)/2);
    insert(ou,(begin+end)/2+1,end);
    if(left[ji]==l1)(*l)=left[ji]+left[ou];
    else (*l)=left[ji];
    if(right[ou]==l2)(*r)=right[ou]+right[ji];
    else (*r)=right[ou];
    max[root]=bigger(bigger(max[ji],max[ou]),left[ou]+right[ji]);

}
int main()
{short n,ppp;
long p;
scanf("%d%d",&n,&p);
memset(stop,0,L*sizeof(char));
stop[0]=1;max[0]=left[0]=right[0]=n;
while(p--)
{scanf("%d",&ppp);
if(ppp==3)printf("%dn",max[0]);
else {scanf("%d%d",&a,&b);b+=a-1;a--;b--;key=ppp;insert(0,0,n-1);}
}
return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *