Pagini recente » Cod sursa (job #1109882) | Cod sursa (job #2091909) | Cod sursa (job #937787) | Cod sursa (job #2315641) | Cod sursa (job #2920904)
#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[800001];
vector<bool>dirty(800001,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)
{
if(st==dr)
{
aint[nod].sum=aint[nod].pre=aint[nod].suf=aint[nod].elemente=1;
return;
}
int m=(st+dr)/2;
build(2*nod,st,m);
build(2*nod+1,m+1,dr);
aint[nod]=comb(aint[2*nod],aint[2*nod+1]);
}
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);
}
}
}