Cod sursa(job #3161199)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 26 octombrie 2023 08:30:36
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<climits>
#include<iomanip>
#include<cstring>
#include<bitset>

#define DIM 100000

using namespace std;

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

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

struct info{
    long long ssmax;
    long long ssst;
    long long ssdr;
    long long sum;

    long long lazy = 0;
}aint[5*DIM];

long long n,m,sol,a,b,x,t;

void createInfo(int nod,int st,int dr){
    int mid = (st+dr)/2;
    aint[nod].ssmax = max(max(aint[2*nod].ssmax,aint[2*nod+1].ssmax),aint[2*nod].ssdr+aint[2*nod+1].ssst);

    if(aint[2*nod].sum == mid-st+1){
        aint[nod].ssst = aint[2*nod].sum+aint[2*nod+1].ssst;
    }else{
        aint[nod].ssst = aint[2*nod].ssst;
    }

    if(aint[2*nod+1].sum == dr-mid){
        aint[nod].ssdr = aint[2*nod].ssdr + aint[2*nod+1].sum;
    }else{
        aint[nod].ssdr = aint[2*nod+1].ssdr;
    }

    aint[nod].sum = aint[2*nod].sum+aint[2*nod+1].sum;
}

void propag(int nod,int st,int dr){
    if(aint[nod].lazy != 0){
        if(st!=dr){

            int mid = (st+dr)/2;
            int val = aint[nod].lazy + (aint[nod].lazy == -1);

            aint[2*nod].ssmax = aint[2*nod].ssst = aint[2*nod].ssdr = aint[2*nod].sum = val * (mid-st+1);

            aint[2*nod+1].ssmax = aint[2*nod+1].ssst = aint[2*nod+1].ssdr = aint[2*nod+1].sum = val * (dr-mid);

            aint[2*nod+1].lazy = aint[2*nod].lazy = aint[nod].lazy = aint[nod].lazy;

        }


        aint[nod].lazy = 0;
    }
}

void build(long long nod,long long st,long long dr){

    if(st == dr){
        aint[nod].ssmax = 1;
        aint[nod].ssst = 1;
        aint[nod].ssdr = 1;
        aint[nod].sum = 1;
    }else{

        long long mid = (st+dr)/2;

        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);

        createInfo(nod,st,dr);
    }
}

void afisare(long long nod,long long st,long long dr){
    propag(nod,st,dr);

    if(st == dr){
        cout<<st<<"="<<aint[nod].ssmax<<'\n';
    }else{

        long long mid = (st+dr)/2;

        cout<<st<<"-"<<dr<<"= ["<<aint[nod].ssmax<<" "<<aint[nod].ssst<<" "<<aint[nod].ssdr<<" "<<aint[nod].sum<<"]"<<'\n';

        afisare(2*nod,st,mid);
        afisare(2*nod+1,mid+1,dr);
    }
    if(nod == 1){
        cout<<'\n';
    }
}

void update(int nod,int st,int dr,int a,int b,int val){

    propag(nod,st,dr);

    if(a<=st && dr<=b){
        val += (val==-1);
        aint[nod].ssmax = aint[nod].ssst = aint[nod].ssdr = aint[nod].sum = aint[nod].lazy = val;
    }else{

        long long mid = (st+dr)/2;

        if(a<=mid){
            update(2*nod,st,mid,a,b,val);
        }
        if(mid+1<=b){
            update(2*nod+1,mid+1,dr,a,b,val);
        }

        createInfo(nod,st,dr);
    }

}


signed main(){

    f>>n>>m;
    build(1,1,n);

    for(long long i=1;i<=m;i++){
        f>>t;
        if(t==1){
            f>>a>>x;
            b=a+x-1;
            update(1,1,n,a,b,-1);
        }else if(t==2){
            f>>a>>x;
            b = a+x-1;
            update(1,1,n,a,b,1);
        }else{
            /*afisare(1,1,n);
            cout<<'\n';
            for(int i=1;i<=n;i++){
                cout<<query(1,1,n,i,i).ssmax<<" ";
            }
            cout<<'\n'<<'\n';*/

            g<<aint[1].ssmax<<'\n';
        }

    }

    f.close();
    g.close();
    return 0;
}