Cod sursa(job #540827)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 24 februarie 2011 14:41:43
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<stdio.h>

#define maxim(a,b) (a>b ? a : b)
#define NMAX 100005

int n,k,p[3*NMAX];
int A[3*NMAX],B[3*NMAX],C[3*NMAX];


void update(int n,int st,int dr,int a,int b,int val)
{
    if(a<=st && dr<=b)
    {
        p[n]=val;
        if(val==-1)
            val=dr-st+1;
        else
            val=0;
        A[n]=B[n]=C[n]=val;
        return ;
    }
    int mij=(st+dr)/2;

    if(p[n])
    {
        update(2*n,st,mij,st,mij,p[n]);
        update(2*n+1,mij+1,dr,mij+1,dr,p[n]);
        p[n]=0;
    }
    
    if(a<=mij)
        update(2*n,st,mij,a,b,val);
    if(b>mij)
        update(2*n+1,mij+1,dr,a,b,val);
        
    B[n]=B[2*n];
    if(B[n]==mij-st+1)
        B[n]+=B[2*n+1];
        
    C[n]=C[2*n+1];
    if(C[n]==dr-mij)
        C[n]+=C[2*n];

    A[n]=maxim(A[2*n],A[2*n+1]);
    A[n]=maxim(A[n],C[2*n]+B[2*n+1]);
}

int main ()
{
    int i,tip,a,b;
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    scanf("%d%d",&n,&k);
    
    update(1,1,n,1,n,-1);

    for(i=1;i<=k;i++)
    {
        scanf("%d",&tip);
        if(tip==1)
        {
            scanf("%d%d",&a,&b);
            update(1,1,n,a,a+b-1,1);
        }
        else if(tip==2)
        {
            scanf("%d%d",&a,&b);
            update(1,1,n,a,a+b-1,-1);
        }
        else
            printf("%d\n",A[1]);
    }
    return 0;
}