Cod sursa(job #3297907)

Utilizator Tudor_11Tudor Ioan Calin Tudor_11 Data 24 mai 2025 12:15:14
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
struct aint
{
    int st,dr,mx;
};
int lazy[400001];
aint tree[400001];
void build(int node,int st,int dr)
{
    if(st==dr)
    {
        tree[node].st=1;
        tree[node].dr=1;
        tree[node].mx=1;
    }
    else
    {
        int mid=(st+dr)/2;
        build(2*node,st,mid);
        build(2*node+1,mid+1,dr);
    }
}
void update_mx(int node)
{
    tree[node].st=tree[2*node].st;
    tree[node].dr=tree[2*node+1].dr;
    tree[node].mx=max(tree[2*node].dr+tree[2*node+1].st,max(tree[2*node].mx,tree[2*node+1].mx));
}
void propagate(int node,int st,int dr)
{
    if(lazy[node]==1)
    {
        lazy[node]=0;
        tree[node].st=0;
        tree[node].dr=0;
        tree[node].mx=0;
        if(st!=dr)
        {
            lazy[2*node]=1;
            lazy[2*node+1]=1;
        }
    }
    else
    {
        lazy[node]=0;
        tree[node].st=dr-st+1;
        tree[node].dr=dr-st+1;
        tree[node].mx=dr-st+1;
        if(st!=dr)
        {
            lazy[2*node]=-1;
            lazy[2*node+1]=-1;
        }
    }
}
void update(int node,int st,int dr,int a,int b,int val)
{
    if(a<=st && dr<=b)
    {
        lazy[node]=val;
    }
    else
    {
        int mid=(st+dr)/2;
        propagate(node,st,dr);
        if(a<=mid) update(2*node,st,mid,a,b,val);
        if(b>mid) update(2*node+1,mid+1,dr,a,b,val);
        propagate(2*node,st,mid);
        propagate(2*node+1,mid+1,dr);
        update_mx(node);
    }
}
int main()
{
    int n,p,c,m,pos;
    fin>>n>>p;
    build(1,1,n);
    for(int i=1;i<=p;i++)
    {
       fin>>c;
       if(c==1)
       {
           fin>>pos>>m;
           update(1,1,n,pos,pos+m-1,1);
       }
       else if(c==2)
       {
           fin>>pos>>m;
           update(1,1,n,pos,pos+m-1,-1);
       }
       else
       {
           propagate(1,1,n);
           fout<<tree[1].mx<<'\n';
       }
    }
    return 0;
}