| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 901613 | imarn | Progression (NOI20_progression) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=3e5+5;
struct node{
ll al,ar,mxl,mxr,mx,sz,dl,dr;
node operator+(node b){
node tmp;tmp.al=al;tmp.ar=b.ar;tmp.sz=sz+b.sz;
tmp.mxl=max(mxl,1ll*2);tmp.mx=max({mx,b.mx,1ll*2});
tmp.mxr=max(b.mxr,1ll*2);
if(sz==0&&b.sz==0)return {0,0,0,0,0,0,0};
else if(sz==0)return b;
else if(b.sz==0)return {al,ar,mxl,mxr,mx,sz,dl,dr};
else if(sz==1&&b.sz==1){
tmp.mxl=2;tmp.mxr=2;tmp.mx=2;
tmp.dl=b.al-ar,tmp.dr=b.al-ar;
}
else if(sz==1){
if(b.al-ar==b.dl)tmp.mxl = max(tmp.mxl,1+b.mxl);
if(b.al-ar==b.dl&&b.mxr==b.sz)tmp.mxr=max(tmp.mxr,1+b.mxr);
if(b.al-ar==b.dl)tmp.mx=max(tmp.mx,1+b.mxl);
tmp.dr=b.dr;tmp.dl=b.al-ar;
}
else if(b.sz==1){
if(b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+1});
if(b.al-ar==dr)tmp.mxr=max(tmp.mxr,1+mxr);
if(b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+1);
tmp.dr=b.al-ar;tmp.dl=dl;
}
else {
if(dr==b.dl&&b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+b.mxl});
if(dr==b.dl&&b.al-ar==dr&&b.mxr==b.sz)tmp.mxr=max({tmp.mxr,mxr+b.mxr});
if(dr==b.dl&&b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+b.mxl);tmp.dl=dl,tmp.dr=b.dr;
if(b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+1});
if(b.al-ar==b.dl&&b.mxr==b.sz)tmp.mxr=max({tmp.mxr,b.mxr+1});
if(b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+1);
if(b.al-ar==b.dl)tmp.mx=max(tmp.mx,b.mxl+1);
}return tmp;
}
}t[4*N];
ll a[N];
pii lz[4*N];
bool lzc[4*N]{0};
void push(int i,int l,int r){
clr(i,l,r);
t[i].al+=lz[i].f+l*lz[i].s;
t[i].ar+=lz[i].f+r*lz[i].s;
t[i].dl+=lz[i].s;t[i].dr+=lz[i].s;
if(l<r){
lz[2*i].f+=lz[i].f;lz[2*i].s+=lz[i].s;
lz[2*i+1].f+=lz[i].f;lz[2*i+1].s+=lz[i].s;
}lz[i]={0,0};
}
void clr(int i,int l,int r){
if(lzc[i]){
lz[i]={0,0};
t[i]={0,0,r-l+1,r-l+1,r-l+1,r-l+1,0,0};
if(l<r){
lzc[2*i]=lzc[2*i+1]=lzc[i];
lz[2*i]=lz[2*i+1]={0,0};
}lzc[i]=0;
}
}
void build(int i,int l,int r){
if(l==r)return void(t[i]={a[l],a[l],1,1,1,1,0,0});
int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
t[i]=t[2*i]+t[2*i+1];
}
node qr(int i,int l,int r,int tl,int tr){
clr(i,l,r);push(i,l,r);
if(r<tl||l>tr)return {0,0,0,0,0,0,0,0};
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return qr(2*i,l,m,tl,tr)+qr(2*i+1,m+1,r,tl,tr);
}
void upd(int i,int l,int r,int tl,int tr,ll S,ll L,ll C){
clr(i,l,r);push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i].f+=S-L*C;lz[i].s+=C;push(i,l,r);
return;
}int m=(l+r)>>1;
upd(2*i,l,m,tl,tr,S,L,C);upd(2*i+1,m+1,r,tl,tr,S,L,C);
t[i]=t[2*i]+t[2*i+1];
}
void setzero(int i,int l,int r,int tl,int tr){
clr(i,l,r);push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lzc[i]=1;clr(i,l,r);return;
}int m=(l+r)>>1;
setzero(2*i,l,m,tl,tr);setzero(2*i+1,m+1,r,tl,tr);
t[i]=t[2*i]+t[2*i+1];
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0;i<4*N;i++)lz[i]={0,0};
build(1,1,n);
while(q--){
int x;cin>>x;
if(x==1){
ll l,r,s,c;cin>>l>>r>>s>>c;
upd(1,1,n,l,r,s,l,c);
}
if(x==2){
ll l,r,s,c;cin>>l>>r>>s>>c;
setzero(1,1,n,l,r);
upd(1,1,n,l,r,s,l,c);
}
if(x==3){
int l,r;cin>>l>>r;
cout<<qr(1,1,n,l,r).mx<<'\n';
}
}
}