Cod sursa(job #3338342)

Utilizator Belea_DariusBelea Mihai Darius Belea_Darius Data 2 februarie 2026 19:08:22
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>
#define MAXN 400000

using namespace std;

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

struct cam{
    int pref, suff, best;
    bool toate;
} aint[4 * MAXN];

cam combine(cam A, cam B, int lenA, int lenB){
    cam C;

    C.pref = A.pref;
    if(A.pref == lenA){
        C.pref += B.pref;
    }

    C.suff = B.suff;
    if(B.suff == lenB){
        C.suff += A.suff;
    }

    C.best = max(max(A.best, B.best), A.suff + B.pref);
    C.toate = false;
    return C;
}
void build(int nod, int st, int dr){
    int mij;
    aint[nod].pref = aint[nod].suff = aint[nod].best = dr - st + 1;
    aint[nod].toate = true;
    if(st < dr){
        mij = (st + dr) / 2;
        build(2 * nod, st, mij);
        build(2 * nod + 1, mij + 1, dr);
    }
}
void update(int nod, int st, int dr, int l, int r, int val){
    int mij;
    if(l <= st && dr <= r){
        aint[nod].pref = aint[nod].suff = aint[nod].best = val * (dr - st + 1);
        aint[nod].toate = true;
    }else{
        mij = (st + dr) / 2;
        if(aint[nod].toate){
            aint[nod].toate = false;
            if(aint[nod].pref == 0){
                aint[2 * nod].pref = aint[2 * nod].suff = aint[2 * nod].best = 0;
                aint[2 * nod + 1].pref = aint[2 * nod + 1].suff = aint[2 * nod + 1].best = 0;
            }else{
                aint[2 * nod].pref = aint[2 * nod].suff = aint[2 * nod].best = mij - st + 1;
                aint[2 * nod + 1].pref = aint[2 * nod + 1].suff = aint[2 * nod + 1].best = dr - mij;
            }
            aint[2 * nod].toate = aint[2 * nod + 1].toate = true;
        }
        if(l <= mij){
            update(2 * nod, st, mij, l, r, val);
        }
        if(r > mij){
            update(2 * nod + 1, mij + 1, dr, l, r, val);
        }
        aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1], mij - st + 1, dr - mij);
    }
}

int main()
{
    int n, p, tip, i, m;

    fin >> n >> p;
    build(1, 1, n);

    while(p --){
        fin >> tip;

        if(tip == 3){
            fout << aint[1].best << "\n";
        }else if(tip == 1){
            fin >> i >> m;
            update(1, 1, n, i, i + m - 1, 0);
        }else{
            fin >> i >> m;
            update(1, 1, n, i, i + m - 1, 1);
        }
    }
    return 0;
}