Cod sursa(job #2760669)

Utilizator Tudor_StefanaStefana Tudor Tudor_Stefana Data 28 iunie 2021 17:19:42
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb

#include <bits/stdc++.h>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
const int NMAX = 100005;
struct idk{
    int nr,st,dr,lazy;
};
idk aint[4*NMAX];
int n,m,c,ok=1,a,b;
void update(int nod,int st,int dr,int x,int y){
    if(x<=st and dr<=y){
        if(ok==1) aint[nod].nr=aint[nod].st=aint[nod].dr=dr-st+1;
        else      aint[nod].nr=aint[nod].st=aint[nod].dr=0;
        aint[nod].lazy=1;
        return;
    }
    int mij=(st+dr)/2;
    if(aint[nod].lazy==1){
        aint[nod].lazy=0;
        if(aint[nod].nr!=0){
            aint[2*nod].nr=aint[2*nod].st=aint[2*nod].dr=mij-st+1;
            aint[2*nod+1].nr=aint[2*nod+1].st=aint[2*nod+1].dr=dr-mij;
        } else {
            aint[2*nod].nr=aint[2*nod+1].nr=0;
            aint[2*nod].st=aint[2*nod+1].st=0;
            aint[2*nod].dr=aint[2*nod+1].dr=0;
        }
        aint[2*nod].lazy=aint[2*nod+1].lazy=1;
    }
    if(mij>=x) update(2*nod,st,mij,x,y);
    if(y>mij) update(2*nod+1,mij+1,dr,x,y);
    aint[nod].nr=max(aint[2*nod].dr+aint[2*nod+1].st,max(aint[2*nod].nr,aint[2*nod+1].nr));
    aint[nod].st=aint[2*nod].st;
    if(aint[2*nod].st==mij-st+1)
        aint[nod].st+=aint[2*nod+1].st;
    aint[nod].dr=aint[2*nod+1].dr;
    if(aint[2*nod+1].dr==dr-mij)
        aint[nod].dr+=aint[2*nod].dr;
}
int main()
{
    fin >> n >> m;
    update(1,1,n,1,n);
    for(int i=1;i<=m;i++){
        fin >> c;
        if(c==3){
            fout << max(aint[1].nr,max(aint[1].st,aint[1].dr)) << '\n';
            continue;
        }
        fin >> a >> b;
        if(c==1) ok=0;
        else     ok=1;
        update(1,1,n,a,a+b-1);
    }
    return 0;
}