Cod sursa(job #3363018)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 13 august 2026 13:20:39
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;

ifstream fin("hotel.in");
ofstream fout("hotel.out");

int t;
struct nod{
    int pref, suff, best, sum, lazy;
} aint[4 * MAXN + 1];

nod combine(nod A, nod B){
    nod rez;

    rez.sum = A.sum + B.sum;
    rez.pref = A.pref;
    if(A.sum == 0){
        rez.pref += B.pref;
    }
    rez.suff = B.suff;
    if(B.sum == 0){
        rez.suff += A.suff;
    }
    rez.best = max(A.best, max(B.best, A.suff + B.pref));
    rez.lazy = 0;

    return rez;
}

void build(int nod, int st, int dr){
    int mij;

    if(st == dr){
        aint[nod].pref = aint[nod].suff = aint[nod].best = 1;
        aint[nod].sum = 0;
    }else{
        mij = (st + dr) / 2;

        build(2 * nod, st, mij);
        build(2 * nod + 1, mij + 1, dr);
        aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
    }
}

void un_lazy(int nod, int st, int dr){
    if(aint[nod].lazy == 1){
        aint[nod].best = aint[nod].suff = aint[nod].pref = 0;
        aint[nod].sum = dr - st + 1;
        if(st != dr){
            aint[2 * nod].lazy = aint[2 * nod + 1].lazy = 1;
        }
    }else if(aint[nod].lazy == 2){
        aint[nod].best = aint[nod].suff = aint[nod].pref = dr - st + 1;
        aint[nod].sum = 0;
        if(st != dr){
            aint[2 * nod].lazy = aint[2 * nod + 1].lazy = 2;
        }
    }
    aint[nod].lazy = 0;
}

void update(int nod, int st, int dr, int a, int b){
    int mij;

//    printf("nod = %d, st = %d, dr = %d, best = %d, suff = %d, pref = %d, l%d a%d b%d\n", nod, st, dr, aint[nod].best, aint[nod].suff, aint[nod].pref, aint[nod].lazy, a, b);

    if(aint[nod].lazy){
        un_lazy(nod, st, dr);
    }
    if(a <= st && dr <= b){
        if(t == 1){
            aint[nod].best = aint[nod].suff = aint[nod].pref = 0;
            aint[nod].sum = dr - st + 1;
            if(st != dr){
                aint[2 * nod].lazy = aint[2 * nod + 1].lazy = 1;
            }
        }else{
            aint[nod].best = aint[nod].suff = aint[nod].pref = dr - st + 1;
            aint[nod].sum = 0;
            if(st != dr){
                aint[2 * nod].lazy = aint[2 * nod + 1].lazy = 2;
            }
        }
    }else{
        mij = (st + dr) / 2;


        if(b <= mij){
            update(2 * nod, st, mij, a, b);
        }else if(a > mij){
            update(2 * nod + 1, mij + 1, dr, a, b);
        }else{
            update(2 * nod, st, mij, a, b);
            update(2 * nod + 1, mij + 1, dr, a, b);
        }
        if(aint[2 * nod].lazy){
            un_lazy(2 * nod, st, mij);
        }
        if(aint[2 * nod + 1].lazy){
            un_lazy(2 * nod + 1, mij + 1, dr);
        }
        aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
    }
//    printf("nod = %d, st = %d, dr = %d, best = %d, suff = %d, pref = %d, l%d a%d b%d\n", nod, st, dr, aint[nod].best, aint[nod].suff, aint[nod].pref, aint[nod].lazy, a, b);
}


int main()
{
    int n, p, i, a, b;

    fin >> n >> p;

    build(1, 1, n);
    for(i = 1; i < 4 * MAXN; i++){
        aint[i].lazy = 0;
    }
    while(p--){
        fin >> t;
        if(t == 3){
            if(aint[1].lazy){
                un_lazy(1, 1, n);
            }
            fout << aint[1].best << "\n";
        }else{
            fin >> a >> b;
            update(1, 1, n, a, a + b - 1);
        }
//        printf("\n\n\n\n\n");
    }
    return 0;
}