Cod sursa(job #3136872)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 8 iunie 2023 23:47:12
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <bits/stdc++.h>
#define DIM 200001

using namespace std;

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

struct nod{
    int prefix, suffix, answer, size, lazy_propagation;
};

vector <nod> aint(4 * DIM);

nod Combine(nod st, nod dr){
    nod answer;
    if(st.size == st.prefix)
        answer.prefix = st.size + dr.prefix;
    else answer.prefix = st.prefix;
    if(dr.size == dr.suffix)
        answer.suffix = dr.size + st.suffix;
    else answer.suffix = dr.suffix;
    answer.answer = max(max(st.answer, dr.answer), max(max(st.prefix, dr.suffix), st.suffix + dr.prefix));
    answer.lazy_propagation = 0;
    answer.size = st.size + dr.size;
    return answer;
}

void Propagate(int node){
    aint[2 * node].prefix = aint[2 * node].suffix = aint[2 * node].answer = ((aint[node].lazy_propagation > 0) * aint[2 * node].size);
    aint[2 * node + 1].prefix = aint[2 * node + 1].suffix = aint[2 * node + 1].answer = ((aint[node].lazy_propagation > 0) * aint[2 * node + 1].size);
    aint[2 * node].lazy_propagation = aint[2 * node + 1].lazy_propagation = aint[node].lazy_propagation;
    aint[node].lazy_propagation = 0;
}

void Build(int node, int st, int dr){
    if(st == dr)
        aint[node].prefix = aint[node].suffix = aint[node].answer = aint[node].size = (dr - st + 1);
    else {
        int mij = (st + dr) >> 1;
        Build(2 * node, st, mij);
        Build(2 * node + 1, mij + 1, dr);
        aint[node] = Combine(aint[2 * node], aint[2 * node + 1]);
    }
}

void Update(int node, int st, int dr, int a, int b, int val){
    if(st >= a && dr <= b){
        aint[node].prefix = aint[node].suffix = aint[node].answer = ((val == 1) * (dr - st + 1));
        aint[node].lazy_propagation = val;
        Propagate(node);
    }
    else {
        if(aint[node].lazy_propagation)
            Propagate(node);
        int mij = (st + dr) >> 1;
        if(a <= mij)
            Update(2 * node, st, mij, a, b, val);
        if(b > mij)
            Update(2 * node + 1, mij + 1, dr, a, b, val);
        aint[node] = Combine(aint[2 * node], aint[2 * node + 1]);
    }
}

int n, Q, task, x, y;

int32_t main(){

    ios :: sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> Q;

    Build(1, 1, n);

    while(Q--){
        fin >> task;
        if(task == 1){
            fin >> x >> y;
            Update(1, 1, n, x, x + y - 1, -1);
        }
        if(task == 2){
            fin >> x >> y;
            Update(1, 1, n, x, x + y - 1, 1);
        }
        if(task == 3)
            fout << aint[1].answer << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}