Cod sursa(job #3289771)

Utilizator IleaIlea Bogdan Ilea Data 28 martie 2025 14:09:23
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.76 kb
#include <iostream>
using namespace std;

#define NMAX 100001
#define def int nod=1, int st=1, int dr=n

struct tree{
    int lz=0;
    int fst, fdr, sz;
    friend bool operator<(tree t1, tree t2){
        return t1.sz<t2.sz;
    }
} aint[NMAX*4];
int n, q, x, y;
void add(def){
    if (aint[nod].lz){
        if (st!=dr){
            aint[2*nod].lz=aint[nod].lz;
            aint[2*nod+1].lz=aint[nod].lz;
        }
        if (aint[nod].lz==1){
            aint[nod].sz=0;
        } else aint[nod].sz=(dr-st+1);
        aint[nod].lz=0;
    }
    if (y<st || dr<x)return;
    if (x<=st && dr<=y){
        aint[nod].sz=0;
        if (st!=dr){
            aint[2*nod].lz=1;
            aint[2*nod+1].lz=1;
        }
        //cout<<st<<" "<<dr<<" -> "<<aint[nod].sz<<" nod: "<<nod<<endl;
        return;
    }
    int mij=(st+dr)/2;
    add(2*nod, st, mij);
    add(2*nod+1, mij+1, dr);
    if (aint[2*nod].sz && aint[2*nod+1].sz){
        //cout<<"c1"<<" - "<<nod<<endl;
        //cout<<aint[2*nod].sz<<" "<<aint[2*nod+1].sz<<endl;
        if (aint[2*nod].fdr==aint[2*nod+1].fst-1){
            aint[nod].fst=aint[2*nod].fst;
            aint[nod].fdr=aint[2*nod+1].fdr;
            aint[nod].sz=(abs(aint[nod].fdr-aint[nod].fst)+1);
            return;
        }
        aint[nod]=max(aint[2*nod], aint[2*nod+1]);
        return;
    }
    if (aint[2*nod].sz){
        //cout<<"c2"<<" - "<<nod<<" from: "<<2*nod<<" - "<<aint[2*nod].sz<<endl;
        aint[nod]=aint[2*nod];
        return;
    }
    if (aint[2*nod+1].sz){
        //cout<<"c3"<<" - "<<nod<<endl;
        aint[nod]=aint[2*nod+1];
        return;
    }
    //cout<<"c4"<<" - "<<nod<<endl;
    aint[nod]={.lz=0, .fst=st, .fdr=dr, .sz=0};
}
void del(def){
    if (aint[nod].lz){
        if (st!=dr){
            aint[2*nod].lz=aint[nod].lz;
            aint[2*nod+1].lz=aint[nod].lz;
        }
        if (aint[nod].lz==1){
            aint[nod].sz=0;
        } else aint[nod].sz=(dr-st+1);
        aint[nod].lz=0;
    }
    if (y<st || dr<x)return;
    if (x<=st && dr<=y){
        aint[nod].sz=dr-st+1;
        aint[nod].fst=st;
        aint[nod].fdr=dr;
        if (st!=dr){
            aint[2*nod].lz=-1;
            aint[2*nod+1].lz=-1;
        }
        //cout<<st<<" "<<dr<<" -> "<<aint[nod].sz<<" nod: "<<nod<<endl;
        return;
    }
    int mij=(st+dr)/2;
    del(2*nod, st, mij);
    del(2*nod+1, mij+1, dr);
    if (aint[2*nod].sz && aint[2*nod+1].sz){
        //cout<<"c1"<<" - "<<nod<<endl;
        //cout<<aint[2*nod].sz<<" "<<aint[2*nod+1].sz<<endl;
        if (aint[2*nod].fdr==aint[2*nod+1].fst-1){
            aint[nod].fst=aint[2*nod].fst;
            aint[nod].fdr=aint[2*nod+1].fdr;
            aint[nod].sz=(abs(aint[nod].fdr-aint[nod].fst)+1);
            return;
        }
        //cout<<"out\n";
        aint[nod]=max(aint[2*nod], aint[2*nod+1]);
        return;
    }
    if (aint[2*nod].sz){
        //cout<<"c2"<<" - "<<nod<<" from: "<<2*nod<<" - "<<aint[2*nod].sz<<endl;
        aint[nod]=aint[2*nod];
        return;
    }
    if (aint[2*nod+1].sz){
        //cout<<"c3"<<" - "<<nod<<endl;
        aint[nod]=aint[2*nod+1];
        return;
    }
    //cout<<"c4"<<" - "<<nod<<endl;
    aint[nod]={.lz=0, .fst=st, .fdr=dr, .sz=0};
}
void init(def){
    //cout<<nod<<" - "<<st<<" "<<dr<<endl;

/**
1 - 1 12
2 - 1 6
4 - 1 3
8 - 1 2
16 - 1 1
17 - 2 2
9 - 3 3
5 - 4 6
10 - 4 5
20 - 4 4
21 - 5 5
11 - 6 6
3 - 7 12
6 - 7 9
12 - 7 8
24 - 7 7
25 - 8 8
13 - 9 9
7 - 10 12
14 - 10 11
28 - 10 10
29 - 11 11
15 - 12 12
*/
    if (st==dr){
        aint[nod].sz=1;
        aint[nod].fst=st;
        aint[nod].fdr=st;
        aint[nod].lz=0;
        return;
    }
    int mij=(st+dr)/2;
    init(2*nod, st, mij);
    init(2*nod+1, mij+1, dr);
    aint[nod].fst=st, aint[nod].fdr=dr;
    aint[nod].sz=(dr-st+1);
}
void solve(void){
    cin>>n>>q;
    init();
    while (q--){
        int op, i, m;
        cin>>op;
        if (op==1){
            cin>>i>>m;
            x=i, y=i+m-1;
            //cout<<" --- "<<x<<" -- "<<y<<endl;
            //cout<<"\n\nSTART UPDATE\n\n\n";
            add();
        } else if (op==2){
            cin>>i>>m;
            x=i, y=i+m-1;
            //cout<<"\n\nSTART UPDATE\n\n\n";
            del();
        } else {
            cout<<aint[1].sz<<"\n";
            //cout<<"*** "<<aint[1].fst<<" - "<<aint[1].fdr<<"\n";
        }
    }
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifdef LOCAL
        freopen("date.in", "r", stdin);
        freopen("log.txt", "w", stdout);
    #else
        freopen("hotel.in", "r", stdin);
        freopen("hotel.out", "w", stdout);
    #endif
    solve();
    return 0;
}