Cod sursa(job #3300832)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 19 iunie 2025 13:30:33
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;

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

//0-vin oameni
//1-pleaca oameni

const int nmax=4e5+5;

int n, m, aint[nmax], st[nmax], dr[nmax], lazy[nmax];

void pushlazy (int node, int left, int right)
{
    if (lazy[node]==-1)
        return;
    if (lazy[node]==1)
        st[node]=dr[node]=aint[node]=right-left+1;
    else
        st[node]=dr[node]=aint[node]=0;
    if (left<right)
    {
        lazy[2*node]=lazy[node];
        lazy[2*node+1]=lazy[node];
    }
    lazy[node]=-1;
}

void update (int node, int left, int right, int a, int b, int val)
{
    pushlazy(node,left,right);
    if (a<=left && right<=b)
    {
        lazy[node]=val;
        return;
    }
    int mij=(left+right)/2;
    if (a <= mij)
        update(2*node,left,mij,a,b,val);
    if (mij+1<=b)
        update(2*node+1,mij+1,right,a,b,val);
    pushlazy(2*node,left,mij);
    pushlazy(2*node+1,mij+1,right);
    aint[node]=max(dr[2*node]+st[2*node+1],max(aint[2*node],aint[2*node+1]));
    if (st[2*node]==mij-left+1)
        st[node]=st[2*node]+st[2*node+1];
    else
        st[node]=st[2*node];
    if (dr[2*node+1]==right-mij)
        dr[node]=dr[2*node+1]+dr[2*node];
    else
        dr[node]=dr[2*node+1];
}

int main()
{
    fin >> n >> m;
    for (int i=0; i<=4*n; i++)
        lazy[i]=-1;
    update(1,1,n,1,n,1);
    for (int i=1; i<=m; i++)
    {
        int cer;
        fin >> cer;
        if (cer==1)
        {
            int left, lg;
            fin >> left >> lg;
            update(1,1,n,left,left+lg-1,0);
        }
        else if (cer==2)
        {
            int left, lg;
            fin >> left >> lg;
            update(1,1,n,left,left+lg-1,1);
        }
        else
        {
            pushlazy(1,1,n);
            fout << aint[1] << '\n';
        }
    }
    return 0;
}