Cod sursa(job #2055944)

Utilizator cipri321Marin Ciprian cipri321 Data 3 noiembrie 2017 22:34:28
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#define DIM 3*100000+5
using namespace std;
ifstream fi("hotel.in");
ofstream fo("hotel.out");
int n,p;
int tip,inc,sf;
int A[DIM]/*secv maxima cu camere libere*/,B[DIM]/*camere libere inceput*/, C[DIM]/*camere libere sfarsit*/;
void init(int nod, int st, int dr)
{
    A[nod]=B[nod]=C[nod]=dr-st+1;
    if(st==dr) return;
    int m=st+(dr-st)/2;
    init(2*nod,st,m);
    init(2*nod+1,m+1,dr);
}

void update(int nod, int st, int dr,int val,int a,int b)
{
    if(a<=st && dr<=b)
    {
        A[nod]=B[nod]=C[nod]=val*(dr-st+1);
        return;
    }
    int m=st+(dr-st)/2;

    if(A[nod]==0)
        A[2*nod]=B[2*nod]=C[2*nod]=A[2*nod+1]=B[2*nod+1]=C[2*nod+1]=0;
    if(A[nod]==dr-st+1)
    {
        A[2*nod]=B[2*nod]=C[2*nod]=m-st+1;
        A[2*nod+1]=B[2*nod+1]=C[2*nod+1]=dr-m;
    }

    if(a<=m) update(2*nod,st,m,val,a,b);
    if(m<b) update(2*nod+1,m+1,dr,val,a,b);

    B[nod]=B[2*nod];
    if(B[2*nod]==m-st+1) B[nod]+=B[2*nod+1];
    C[nod]=C[2*nod+1];
    if(C[2*nod+1]==dr-m) C[nod]+=C[2*nod];
    A[nod]=max( max(A[2*nod],A[2*nod+1]), C[2*nod]+B[2*nod+1] );
}
int main()
{
    fi>>n>>p;
    init(1,1,n);
    for(int q=1; q<=p; q++)
    {
        fi>>tip;
        if(tip==1||tip==2)
        {
            fi>>inc>>sf;
            int u=0;
            if(tip==2) u=1;
            update(1,1,n,u,inc,sf+inc-1);
        }
        else
            fo<<A[1]<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}