Cod sursa(job #2136790)

Utilizator refugiatBoni Daniel Stefan refugiat Data 20 februarie 2018 11:02:29
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream si("hotel.in");
ofstream so("hotel.out");
int n,m;

struct nod {
    int st,dr,maxx;
} a[400005];

void gen(int nod, int st, int dr) {
    int mij=(st+dr)/2;
    a[nod].st=a[nod].dr=a[nod].maxx=dr-st+1;
    if(mij!=st)
        gen(nod*2,st,mij);
    if(mij!=dr)
        gen(nod*2+1,mij,dr);
}

void update(int nod,int l,int r,int st,int dr,int caz) {
    if(dr<l||st>r||l>r)
        return;
    if(st<=l&&r<=dr) {
        if(caz==1)
            a[nod].st=a[nod].dr=a[nod].maxx=r-l+1;
        else
            a[nod].st=a[nod].dr=a[nod].maxx=0;
        return;
    }
    int m=(l+r)/2;
    if(a[nod].maxx==0) {
        a[nod<<1].st=a[nod<<1].dr=a[nod<<1].maxx=0;
        a[nod<<1|1].st=a[nod<<1|1].dr=a[nod<<1|1].maxx=0;
    }
    else
        if(a[nod].maxx==r-l+1) {
            a[nod<<1].st=a[nod<<1].dr=a[nod<<1].maxx=m-l+1;
            a[nod<<1|1].st=a[nod<<1|1].dr=a[nod<<1|1].maxx=r-m;
        }
    update(nod<<1,l,m,st,dr,caz);
    update(nod<<1|1,m+1,r,st,dr,caz);
    a[nod].st=a[nod<<1].st;
    if(a[nod<<1].st==m-l+1)
        a[nod].st+=a[nod<<1|1].st;
    a[nod].dr=a[nod<<1|1].dr;
    if(a[nod<<1|1].dr==r-m)
        a[nod].dr+=a[nod<<1].dr;

    a[nod].maxx=max(a[nod<<1].maxx,a[nod<<1|1].maxx);
    a[nod].maxx=max(a[nod].maxx,a[nod<<1].dr+a[nod<<1|1].st);

}
int main()
{
    si>>n>>m;
    for(int i=1;i<=n;i++)
        update(1,1,n,i,i,1);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        si>>x;
        if(x==3)
            so<<a[1].maxx<<'\n';
        else
        {
            si>>y>>z;
            if(x==1)
                update(1,1,n,y,y+z-1,0);
            if(x==2)
                update(1,1,n,y,y+z-1,1);
        }
    }
    return 0;
}