Cod sursa(job #3324758)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 23 noiembrie 2025 12:53:27
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.86 kb
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");

const int Nmax = 100005;
int v[Nmax], lazy[Nmax * 4];
struct ura{
    int best, prefix, sufix;
} aint[Nmax * 4];
void build( int st, int dr, int nod )
{
    if ( st == dr )
    {
        aint[nod] = {1, 1, 1};
        return ;
    }
    aint[nod] = {dr - st + 1, dr - st +1, dr - st + 1};
    //fout << " st = " << st << " dr = " << dr << " aint = " << aint[nod].best << endl;
    int mij = (st + dr) / 2;
    build(st, mij, 2 * nod );
    build(mij + 1, dr, 2 * nod + 1);
}
void propag( int nod, int st, int dr )
{
    if ( lazy[nod] == -1 )
        return ;

     int mij = (st + dr) / 2;
    if ( lazy[nod] == 0 )
    {
        aint[2 * nod] =  {mij - st + 1, mij - st + 1, mij - st + 1};
        aint[2 * nod + 1] = {dr - mij, dr - mij, dr - mij };
    }
    else
        aint[2 * nod] = aint[2 * nod + 1] = {0, 0, 0};
    lazy[ 2 * nod ] = lazy[nod];
    lazy[ 2 * nod + 1] = lazy[nod];

    lazy[nod] = -1;
}
void update( int st, int dr, int nod, int qst, int qdr, int val )
{
    if ( qst <= st && dr <= qdr )
    {
        if ( val == 0 )
            aint[nod] = {dr - st + 1, dr - st +1, dr - st + 1};
        else
            aint[nod] = {0, 0, 0};
        lazy[nod] = val;
        return ;
    }
    int mij = (st + dr) / 2;
    propag(nod, st, dr);
    if ( qst <= mij )
        update(st, mij, nod * 2, qst, qdr, val);
    if ( qdr >= mij + 1 )
        update(mij + 1, dr, nod * 2 + 1, qst, qdr, val);

    aint[nod].best = max(aint[nod * 2 ].best, max(aint[nod * 2 + 1].best, aint[nod * 2].sufix + aint[nod * 2 + 1].prefix));
    if ( mij - st + 1 == aint[nod * 2].prefix )
        aint[nod].prefix = mij - st + 1 + aint[nod * 2 + 1].prefix;
    else
        aint[nod].prefix = aint[nod * 2].prefix;
    if (dr - mij == aint[nod * 2 + 1].sufix )
        aint[nod].sufix = dr - mij + aint[nod * 2].sufix;
    else
        aint[nod].sufix = aint[nod * 2 + 1].sufix;

    //fout << " st = " << st << " dr = " << dr << " nod = " << nod << " ans.best = " << aint[nod].best << " ans.prefix = " << aint[nod].prefix << " ans.sufix = " << aint[nod].sufix << endl;

}
/*ura querry( int st, int dr, int nod, int qst, int qdr )
{
    if ( qst <= st && dr <= qdr )
        return aint[nod];

    int mij = (st + dr) / 2;
    ura ans;
    propag(nod);
    if ( qst <= mij && mij + 1 <= qdr )
    {
        ura a = querry(st, mij, 2 * nod, qst, qdr);
        ura b = querry(mij + 1, dr, 2 * nod + 1, qst, qdr);
        ans.best = max(a.best, max(b.best, a.sufix + b.prefix));
        if ( mij - st + 1 == a.prefix )
            ans.prefix = mij - st + 1 + b.prefix;
        else
            ans.prefix = a.prefix;

        if (dr - mij == b.sufix )
            ans.sufix = dr - mij + a.sufix;
        else
            ans.sufix = b.sufix;
    }
    else if ( qst <= mij )
        ans = querry(st, mij, nod * 2, qst, qdr);
    else
        ans = querry(mij + 1, dr, 2 * nod + 1, qst, qdr);


    fout << " st = " << st << " dr = " << dr << " nod = " << nod << " ans.best = " << ans.best << " ans.prefix = " << ans.prefix << " ans.sufix = " << ans.sufix << endl;
    return ans;
}*/
int main()
{
    int n, i, q;
    fin >> n;


    build(1, n, 1);
    for ( i = 1; i <= 4 * n; ++i )
        lazy[i] = -1;

    fin >> q;
    for ( i = 1; i <= q; ++i )
    {
        int tip, a, b, x;
        fin >> tip;
        if ( tip == 1 )
        {
            fin >> a >> b;
            update(1, n, 1, a, a + b - 1, 1);
        }
        if ( tip == 2 )
        {
            fin >> a >> b;
            update(1, n, 1, a, a + b - 1, 0);
        }
        if ( tip == 3 )
        {
            fout << aint[1].best << "\n";
            //fout << querry(1, n, 1, 1, n).best << '\n';
        }
    }
    return 0;
}