Cod sursa(job #3176581)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 27 noiembrie 2023 13:05:35
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hotel.in");
ofstream cout("hotel.out");
const int NMAX = 100005;
struct Node{
    int sm, suf, pref, c = -1;
};
vector<Node> aint(4 * NMAX);
int n, Q;
void build(int nod, int l, int r){
    const int mid = (l + r) / 2;
    aint[nod] = {r - l + 1, r - l + 1, r - l + 1, -1};

    if(l == r){
        return;
    }

    build(2 * nod, l, mid);
    build(2 * nod + 1, mid + 1, r);
}
void update(int nod, int l, int r, int x, int y, const int val){
    if(l == x and r == y){
        int s = (!val ? r - l + 1 : 0);
        aint[nod] = {s, s, s, val};
        return;
    }

    const int mid = (l + r) / 2;
    if(aint[nod].c != -1){
        if(!aint[nod].c){
            aint[2 * nod].sm = aint[2 * nod].suf = aint[2 * nod].pref = mid - l + 1;
            aint[2 * nod + 1].sm = aint[2 * nod + 1].suf = aint[2 * nod + 1].pref = r - mid;
        }
        else{
            aint[2 * nod].sm = aint[2 * nod].suf = aint[2 * nod].pref = 0;
            aint[2 * nod + 1].sm = aint[2 * nod + 1].suf = aint[2 * nod + 1].pref = 0;
        }
        aint[2 * nod].c = aint[2 * nod + 1].c = aint[nod].c;
        aint[nod].c = -1;
    }

    if(y <= mid)
        update(2 * nod, l, mid, x, y, val);
    
    else if(x > mid)
        update(2 * nod + 1, mid+1, r, x, y, val);
    
    else update(2 * nod, l, mid, x, mid, val), update(2 * nod + 1, mid+1, r, mid+1, y, val);

    aint[nod].sm = max(aint[2 * nod].sm, max(aint[2 * nod + 1].sm, aint[2 * nod].suf + aint[2 * nod + 1].pref));
    aint[nod].pref = aint[2 * nod].pref;
    aint[nod].suf = aint[2 * nod + 1].suf;

    if(aint[nod].pref == mid - l + 1)
        aint[nod].pref += aint[2 * nod + 1].pref;
    
    if(aint[nod].suf == r - mid)
        aint[nod].suf += aint[2 * nod].suf;
}
void print(int nod, int l, int r){
    cout<<l<<" "<<r<<'\n';
    cout<<aint[nod].pref<<" "<<aint[nod].sm<<" "<<aint[nod].suf<<" "<<aint[nod].c<<"\n-----------\n";

    if(l == r)
        return;
    
    int mid = (l + r) / 2;
    print(2 * nod, l, mid);
    print(2 * nod+1, mid+1, r);
}
int main(){
    cin>>n>>Q;
    build(1, 1, n);

    while(Q--){
        int tip;
        cin>>tip;

        if(tip == 1){
            int i, m;
            cin>>i>>m;
            update(1, 1, n, i, i + m - 1, 1);
        }
        else if(tip == 2){
            int i, m;
            cin>>i>>m;
            update(1, 1, n, i, i + m - 1, 0);
        }
        else cout<<aint[1].sm<<'\n';
    }

    // print(1, 1, n);
    return 0;
}