Cod sursa(job #2964253)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 12 ianuarie 2023 18:36:25
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>

using namespace std;
ifstream cin("hotel.in");
ofstream cout("hotel.out");
const int N = 100009;
int i,m,n,p,cer;
struct noduri
{
    int pre,suf,mx,lazy;
}tree[4*N];
noduri Merge(noduri a,noduri b,int lena,int lenb)
{
    noduri c = {0,0,0,-1};
    c.pre = a.pre;
    c.suf = b.suf;
    if(a.pre == lena)c.pre = a.pre + b.pre;
    if(b.suf == lenb)c.suf = b.suf + a.suf;
    c.mx = max(c.pre,max(c.suf,max(a.suf + b.pre,max(a.mx,b.mx))));
    c.lazy = -1;
    return c;
}
void Push(int nod,int st,int dr)
{
    if(tree[nod].lazy == -1 || st==dr)
        return;
    int mij = (st+dr)>>1;
    tree[nod<<1].pre = tree[nod<<1].suf = tree[nod<<1].mx = (1-tree[nod].lazy)*(mij-st+1);
    tree[nod<<1].lazy = tree[nod].lazy;
    tree[nod<<1|1].pre = tree[nod<<1|1].suf = tree[nod<<1|1].mx = (1-tree[nod].lazy)*(dr-mij);
    tree[nod<<1|1].lazy = tree[nod].lazy;

    tree[nod].lazy = -1;
}
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        tree[nod].pre = tree[nod].suf = tree[nod].mx = 1;
        tree[nod].lazy = -1;
        return;
    }
    int mij = (st+dr)>>1;
    build(nod<<1,st,mij);
    build(nod<<1|1,mij+1,dr);

    tree[nod] = Merge(tree[nod<<1],tree[nod<<1|1],mij - st + 1,dr - mij);
}
void update(int nod,int st,int dr,int a,int b,int val)
{
    Push(nod,st,dr);
    if(a<=st&&dr<=b)
    {
        tree[nod].pre = tree[nod].suf = tree[nod].mx = (1-val)*(dr-st+1);
        tree[nod].lazy = val;
        return;
    }
    int mij = (st+dr)/2;
    if(a<=mij)
        update(nod<<1,st,mij,a,b,val);
    if(b>mij)
        update(nod<<1|1,mij+1,dr,a,b,val);

    tree[nod] = Merge(tree[nod<<1],tree[nod<<1|1],mij-st+1,dr-mij);
}

int main()
{
    cin>>n>>p;
    build(1,1,n);
    while(p--)
    {
        cin>>cer;
        if(cer==1)
        {
            cin>>i>>m;
            update(1,1,n,i,i+m-1,1);
        }
        else if(cer==2)
        {
            cin>>i>>m;
            update(1,1,n,i,i+m-1,0);
        }
        else
            cout<<tree[1].mx<<'\n';
    }
    return 0;
}