Cod sursa(job #3260363)

Utilizator paull122Paul Ion paull122 Data 1 decembrie 2024 21:52:53
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>

#define VMAX 100000
#define NMAX 100000
#define LOG 20

#define INF (long long)(1e9)
#define MOD 100003
#define BASE 23

#define BLOCK_SIZE 230
#define ll long long int


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


struct node
{
    int res,cnt;
    int pref,suff;
    int lazy;
} aint[4*NMAX+1];

void build(int i,int st,int dr)
{
    if(st==dr)
    {
        aint[i].cnt=aint[i].suff=aint[i].pref=aint[i].res=1;
    }
    else
    {
        int m = (st+dr)/2;
        build(2*i,st,m);
        build(2*i+1,m+1,dr);
        aint[i].cnt = aint[i].suff = aint[i].pref = aint[i].res = aint[2*i].cnt + aint[2*i+1].cnt;
    }
}

void propag(int i)
{
    if(!aint[i].lazy)
    {
        return;
    }
    if(aint[i].lazy==1)
    {
        aint[2*i].res = aint[2*i].pref = aint[2*i].suff = aint[2*i].cnt;
        aint[2*i+1].res = aint[2*i+1].pref = aint[2*i+1].suff = aint[2*i+1].cnt;
    }
    else
    {
        aint[2*i].res = aint[2*i].pref = aint[2*i].suff = 0;
        aint[2*i+1].res = aint[2*i+1].pref = aint[2*i+1].suff = 0;
    }
    aint[2*i].lazy = aint[2*i+1].lazy = aint[i].lazy;
    aint[i].lazy=0;
}
void update(int i,int st,int dr,int l,int r,int x)
{

    if(l<=st && dr<=r)
    {
        if(x==1)
        {
            aint[i].res = aint[i].pref = aint[i].suff = aint[i].cnt;
        }
        else
        {
            aint[i].res = aint[i].pref = aint[i].suff = 0;
        }
        aint[i].lazy=x;
    }
    else
    {
        propag(i);
        int m = (st+dr)/2;
        if(l<=m)
        {
            update(2*i,st,m,l,r,x);
        }
        if(m+1<=r)
        {
            update(2*i+1,m+1,dr,l,r,x);
        }
        aint[i].pref = aint[2*i].cnt == aint[2*i].res ? aint[2*i].cnt + aint[2*i+1].pref : aint[2*i].pref;
        aint[i].suff = aint[2*i+1].cnt == aint[2*i+1].res ? aint[2*i+1].cnt + aint[2*i].suff : aint[2*i+1].suff;
        aint[i].res = max({aint[2*i].res,aint[2*i+1].res,aint[2*i].suff + aint[2*i+1].pref});
    }
}
int query(int i,int st,int dr,int p)
{
    if(st==dr)
    {
        return aint[i].res;
    }
    else
    {
        propag(i);
        int m = (st+dr)/2;
        if(p<=m)
        {
            return query(2*i,st,m,p);
        }
        return query(2*i+1,m+1,dr,p);
    }
}
int main()
{
    int n,q;
    fin >> n >> q;
    build(1,1,n);
    while(q--)
    {
        int t;
        fin >> t;

        if(t==3)
        {
            fout << aint[1].res << '\n';
        }
        else
        {
            int l,m;
            fin >> l >> m;
            update(1,1,n,l,min(n,l+m-1),t==1 ? -1 : 1);
        }
    }

}