Cod sursa(job #2920905)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 26 august 2022 15:17:42
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#import <algorithm>
#import <vector>
#import <map>
#import <set>
#import <deque>
#import <queue>
#import <cassert>
//#import <cmath>
#import <cstring>
#import <cctype>
#import <cstdlib>
#import <stack>
using namespace std;
struct nod
{
    int pre,suf,elemente,sum,val;
}aint[400001];
vector<bool>dirty(400001,0);
nod comb(const nod l,const nod r)
{
    nod rez;
    rez.elemente=l.elemente+r.elemente;
    rez.pre=l.pre;
    rez.suf=r.suf;
    if(l.pre==l.elemente)
    {
        rez.pre+=r.pre;
    }
    if(r.suf==r.elemente)
    {
        rez.suf+=l.suf;
    }
    rez.sum=max(max(l.sum,r.sum),l.suf+r.pre);
    return rez;
}
void build(int nod,int st,int dr)
{
    aint[nod].sum=aint[nod].pre=aint[nod].suf=aint[nod].elemente=dr-st+1;
    if(st==dr)
    {
        return;
    }
    int m=(st+dr)/2;
    build(2*nod,st,m);
    build(2*nod+1,m+1,dr);
}


void prop(int nod,int st,int dr)
{
    if(!dirty[nod])return;
    dirty[2*nod]=dirty[2*nod+1]=1;
    aint[2*nod].val=aint[2*nod+1].val=aint[nod].val;
    int m=(st+dr)/2;
    aint[2*nod].pre=aint[2*nod].suf=aint[2*nod].elemente=aint[2*nod].sum=aint[2*nod].val*(m-st+1);
    aint[2*nod+1].pre=aint[2*nod+1].suf=aint[2*nod+1].elemente=aint[2*nod+1].sum=aint[2*nod+1].val*(dr-m);
    dirty[nod]=0;
}
int l,r,val;
void update(int nod,int st,int dr)
{
    if(st!=dr)
    {
        prop(nod,st,dr);
    }
    if(l>dr || r<st)return;
    if(l<=st && dr<=r)
    {
        aint[nod].sum=aint[nod].pre=aint[nod].suf=(dr-st+1)*val;
        aint[nod].val=val;
        dirty[nod]=1;
        prop(nod,st,dr);
        return;
    }
    int m=(st+dr)/2;
    update(2*nod,st,m);
    update(2*nod+1,m+1,dr);
    aint[nod]=comb(aint[2*nod],aint[2*nod+1]);
}
/*void print()
{
    cout<<"aintu e:\n";
    for(int i=1;i<=29;i++)
    {
        cout<<i<<' '<<aint[i].pre<<' '<<aint[i].suf<<' '<<aint[i].sum<<'\n';
    }
    cout<<'\n';
}*/
main()
{
    ifstream cin("hotel.in");
    ofstream cout("hotel.out");
    int n,q;
    cin>>n>>q;
    build(1,1,n);
    while(q--)
    {
        int cer;
        cin>>cer;
        if(cer==3)
        {
            cout<<aint[1].sum<<'\n';
        }
        else
        {
            val=cer-1;
            int y;
            cin>>l>>y;
            r=l+y-1;
            update(1,1,n);
        }
    }
}