Cod sursa(job #365436)

Utilizator freak93Adrian Budau freak93 Data 18 noiembrie 2009 18:53:51
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include<fstream>

using namespace std;

const char iname[]="hotel.in";
const char oname[]="hotel.out";
const int maxn=200000;

ifstream f(iname);
ofstream g(oname);

int i,j,n,m,t,x,y;

struct arbore
{
    int left;
    int right;
    int k;
}arb[maxn*2];

void sub(int nod,int left,int right,int start,int finish)
{
    if(start<=left&&right<=finish)
    {
        arb[nod].left=arb[nod].right=arb[nod].k=(right-left)+1;
        return;
    }

    //corectare
    int div=(left+right)>>1;
    if(arb[nod].k==0)
    {
        arb[nod<<1].left=arb[nod<<1].right=arb[nod<<1].k=0;
        arb[(nod<<1)+1].left=arb[(nod<<1)+1].right=arb[(nod<<1)+1].k=0;
    }
    if(arb[nod].k==right-left+1)
    {
        arb[nod<<1].left=arb[nod<<1].right=arb[nod<<1].k=div-left+1;
        arb[(nod<<1)+1].left=arb[(nod<<1)+1].right=arb[(nod<<1)+1].k=right-div;
    }
    if(start<=div)
        sub(nod<<1,left,div,start,finish);
    if(div<finish)
        sub((nod<<1)+1,div+1,right,start,finish);
    int k=arb[nod<<1].left;
    if(k==div-left+1)
        k+=arb[(nod<<1)+1].left;
    arb[nod].left=k;

    k=arb[(nod<<1)+1].right;
    if(k==right-div)
        k+=arb[nod<<1].right;
    arb[nod].right=k;

    k=arb[nod<<1].right+arb[(nod<<1)+1].left;
    k=max(k,arb[nod<<1].k);
    k=max(k,arb[(nod<<1)+1].k);
    arb[nod].k=k;
    arb[nod].k=max(arb[nod].k,arb[nod].left);
    arb[nod].k=max(arb[nod].k,arb[nod].right);
}

void add(int nod,int left,int right,int start,int finish)
{
    if(start<=left&&right<=finish)
    {
        arb[nod].left=arb[nod].right=arb[nod].k=0;
        return;
    }
    int div=(left+right)>>1;
    if(start<=div)
        add(nod<<1,left,div,start,finish);
    if(div<finish)
        add((nod<<1)+1,div+1,right,start,finish);
    int k=arb[nod<<1].left;
    if(k==div-left+1)
        k+=arb[(nod<<1)+1].left;
    arb[nod].left=k;

    k=arb[(nod<<1)+1].right;
    if(k==right-div)
        k+=arb[nod<<1].right;
    arb[nod].right=k;

    k=arb[nod<<1].right+arb[(nod<<1)+1].left;
    k=max(k,arb[nod<<1].k);
    k=max(k,arb[(nod<<1)+1].k);
    arb[nod].k=k;
    arb[nod].k=max(arb[nod].k,arb[nod].left);
    arb[nod].k=max(arb[nod].k,arb[nod].right);
}

void balance(int nod,int left,int right)
{
    arb[nod].k=arb[nod].left=arb[nod].right=right-left+1;
    if(left==right)
    {
        return;
    }
    int div=(left+right)>>1;
    balance(nod<<1,left,div);
    balance((nod<<1)+1,div+1,right);
}

int main()
{
    f>>n>>m;
    balance(1,1,n);
    for(i=1;i<=m;++i)
    {
        f>>t;
        if(t<3)
        {
            f>>x>>y;
            if(t==1)
                add(1,1,n,x,x+y-1);
            else
                sub(1,1,n,x,x+y-1);
        }
        else
            g<<arb[1].k<<"\n";
    }

    f.close();
    g.close();

    return 0;
}