Cod sursa(job #1957455)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 7 aprilie 2017 16:00:44
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <stdio.h>
const int N = 100005;
struct nodArb
{
    int vst,v,vdr;  ///valoarea care porneste din stanga, valoarea maxima, valoarea care se termina in dr
};


int n,m,i,c,x,l,y;
short stare[4*N];         ///stare[i]={ 0=> valoare actualizata, 1=>au venit turisti, 2=> au plecat turisti }
nodArb arb[4*N];

int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

void buildArb(int st,int dr,int nod)     ///construieste arborele de intervale
{
    if(st>dr)
        return;

    if(st==dr)
    {
        arb[nod].vst=arb[nod].v=arb[nod].vdr=1;
        return;
    }

    int m=(st+dr)/2;

    buildArb(st,m,nod*2);
    buildArb(m+1,dr,nod*2+1);

    arb[nod].vst=arb[nod].v=arb[nod].vdr= arb[nod*2].v + arb[nod*2+1].v;
}

void update(int st,int dr,int nod)      ///lazy update
{
    if(st>dr)
        return;

    if(stare[nod] != 0)     ///in caz ca nodul nu este actualizat
    {
        if(st!=dr)
        {
            stare[nod*2]=stare[nod*2+1]=stare[nod];
        }
        if(stare[nod]==1)
        {
            arb[nod].vst=arb[nod].v=arb[nod].vdr=0;
        }
        if(stare[nod]==2)
        {
            arb[nod].vst=arb[nod].v=arb[nod].vdr=dr-st+1;
        }

        stare[nod]=0;
    }

    if(x<=st && dr<=y)  ///incluziune totala
    {
        if(c==1)    ///au venit turisti
        {
            arb[nod].vst=arb[nod].v=arb[nod].vdr=0;
        }
        if(c==2)    ///au plecat turisti
        {
            arb[nod].vst=arb[nod].v=arb[nod].vdr= dr-st+1;
        }

        if(st!=dr)  ///nu este frunza
        {
            stare[nod*2]=stare[nod*2+1]=c;  ///actualizam starea fiilor
        }

        stare[nod]=0;
        return;
    }

    if(x>dr || st>y)        ///fara incluziune
        return;

    ///incluziune partiala
    int m=(st+dr)/2;

    update(st,m,nod*2);
    update(m+1,dr,nod*2+1);

    ///actualizam valoarea din nod
    arb[nod].vst=arb[nod*2].vst;
    if(arb[nod].vst == m-st+1)      ///ocupa tot intervalul
        arb[nod].vst += arb[nod*2+1].vst;

    arb[nod].v=max(max(arb[nod*2].v,arb[nod*2+1].v), arb[nod*2].vdr+arb[nod*2+1].vst);

    arb[nod].vdr=arb[nod*2+1].vdr;
    if(arb[nod].vdr == dr-m)        ///ocupa tot intervalul
        arb[nod].vdr += arb[nod*2].vdr;
}

int main()
{
    FILE *f1,*f2;
    f1=fopen("hotel.in","r");
    f2=fopen("hotel.out","w");

    fscanf(f1,"%d%d",&n,&m);

    buildArb(1,n,1);

    while(m--)
    {
        fscanf(f1,"%d",&c);

        if(c==3)
        {
            fprintf(f2,"%d\n",arb[1].v);
        }
        else
        {
            fscanf(f1,"%d%d",&x,&l);
            y=x+l-1;

            update(1,n,1);
        }
    }


    return 0;
}