Cod sursa(job #3294580)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 25 aprilie 2025 18:50:55
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f ("hotel.in");
ofstream g ("hotel.out");

const int NMAX = 100000;
int N, M;

struct hotel {
    int sdr, sst, ssm, lung, lazy;
};

hotel Ai[4*NMAX+1];

void UpdateSsm(int rad) {
    Ai[rad].sst = Ai[2*rad].sst;
    if (Ai[2*rad].sst == Ai[2*rad].lung) Ai[rad].sst += Ai[2*rad+1].sst;
    //
    Ai[rad].sdr = Ai[2*rad+1].sdr;
    if (Ai[2*rad+1].sdr == Ai[2*rad+1].lung) Ai[rad].sdr += Ai[2*rad].sdr;
    //
    Ai[rad].ssm = max(Ai[2*rad].sdr + Ai[2*rad+1].sst, max(Ai[2*rad].ssm, Ai[2*rad+1].ssm));
}

void Build(int rad, int st, int dr) {
    if (st == dr)
        Ai[rad].sst = Ai[rad].sdr = Ai[rad].ssm = Ai[rad].lung = 1;
    else {
        int m = (st + dr) / 2;
        //
        Build(2*rad, st, m);
        Build(2*rad+1, m+1, dr);
        //
        Ai[rad].sst = Ai[rad].sdr = Ai[rad].ssm = Ai[rad].lung = dr - st + 1;
    }
}

void UpdateNod(int rad, int st, int dr) {
    if (Ai[rad].lazy == 1) {
        Ai[rad].ssm = 0;
        Ai[rad].sst = 0;
        Ai[rad].sdr = 0;
        Ai[rad].lazy = 0;
        //
        if (st != dr) {
            Ai[2*rad].lazy = 1;
            Ai[2*rad+1].lazy = 1;
        }
    } else if (Ai[rad].lazy == 2) {
        Ai[rad].ssm = dr - st + 1;
        Ai[rad].sst = dr - st + 1;
        Ai[rad].sdr = dr - st + 1;
        Ai[rad].lazy = 0;
        //
        if (st != dr) {
            Ai[2*rad].lazy = 2;
            Ai[2*rad+1].lazy = 2;
        }
    }
}

void Update(int rad, int st, int dr, int a, int b, int val) {
    if (a <= st && b >= dr)
        Ai[rad].lazy = val;
    else {
        int m = (st + dr) / 2;
        //
        UpdateNod(rad, st, dr);
        //
        if (a <= m) Update(2*rad, st, m, a, b, val);
        if (b > m) Update(2*rad+1, m+1, dr, a, b, val);
        //
        UpdateNod(2*rad, st, m);
        UpdateNod(2*rad+1, m+1, dr);
        //
        UpdateSsm(rad);
    }
}

int main(){
    f >> N >> M;
    Build(1, 1, N);
    //
    int op, poz, nr;
    while(M--) {
        f >> op;
        //
        if (op == 1) {
            f >> poz >> nr;
            Update(1, 1, N, poz, poz+nr-1, 1);
        } else if (op == 2) {
            f >> poz >> nr;
            Update(1, 1, N, poz, poz+nr-1, 2);
        } else {
            UpdateNod(1, 1, N);
            g << Ai[1].ssm << '\n';
        }
    }
    //
    f.close();
    g.close();
    return 0;
}