Cod sursa(job #1435997)

Utilizator GinguIonutGinguIonut GinguIonut Data 14 mai 2015 21:09:27
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#define dim 100001
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
int a[3*dim],b[3*dim],poz,val,pozst,pozdr,INF,n,p,op,i,c[3*dim],pozi;
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        a[nod]=b[nod]=c[nod]=1;
        return;
    }
    int mijl=st+(dr-st)/2;
    build(2*nod,st,mijl);
    build(2*nod+1,mijl+1,dr);
    a[nod]=b[nod]=c[nod]=a[2*nod]+a[2*nod+1];
}
void upDate(int nod, int st, int dr)
{
    if(st>=pozst&&dr<=pozdr)
    {
        if(op==1)
            a[nod]=b[nod]=c[nod]=0;
        else
            a[nod]=b[nod]=c[nod]=dr-st+1;
        return;
    }
    int mijl=st+(dr-st)/2;
    if(a[nod]==0)
        a[2*nod]=a[2*nod+1]=b[2*nod]=b[2*nod+1]=c[2*nod]=c[2*nod+1]=0;
    if(a[nod]==dr-st+1)
    {
        a[2*nod]=b[2*nod]=c[2*nod]=mijl-st+1;
        a[2*nod+1]=b[2*nod+1]=c[2*nod+1]=dr-mijl;
    }
    if(pozst<=mijl)
        upDate(2*nod,st,mijl);
    if(pozdr>mijl)
        upDate(2*nod+1,mijl+1,dr);
    if(b[2*nod]==mijl-st+1)
        b[nod]=b[2*nod]+b[2*nod+1];
    else
        b[nod]=b[nod*2];
    if(c[2*nod+1]==dr-mijl)
        c[nod]=c[nod*2]+c[2*nod+1];
    else
        c[nod]=c[nod*2+1];
    a[nod]=max(a[2*nod],max(a[2*nod+1],c[2*nod]+b[2*nod+1]));

}
int main()
{
    fin>>n>>p;
    build(1,1,n);
    for(i=1;i<=p;i++)
    {
        fin>>op;
        if(op==3)
        {
            fout<<a[1]<<'\n';
            continue;
        }
        else
        {
            fin>>pozst>>pozi;
            pozdr=pozst+pozi-1;
            upDate(1,1,n);
        }
    }

    return 0;
}