| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 265329 | eohomegrownapps | 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>
using namespace std;
typedef long long ll;
int deltas[300000];
struct Data{
int len = 1;
int maxpref=1;
int maxsuff=1;
ll prefval=0;
ll suffval=0;
int maxlen=1;
ll deltasum = 0;
};
int n;
Data combine(Data &l, Data &r){
Data ans;
ans.len = l.len + r.len;
ans.deltasum = l.deltasum + r.deltasum;
ans.maxpref = l.maxpref;
ans.prefval = l.prefval;
ans.maxsuff = r.maxsuff;
ans.suffval = r.suffval;
if (l.maxpref==l.len&&l.prefval==r.prefval){
ans.maxpref=l.len+r.maxpref;
}
if (r.maxpref==r.len&&r.prefval==l.suffval){
ans.maxsuff=r.len+l.maxsuff;
}
ans.maxlen=max(l.maxlen,r.maxlen);
if (l.suffval==r.prefval){
ans.maxlen=max(ans.maxlen,l.maxsuff+r.maxpref);
}
return ans;
}
Data init(ll ind){
Data ans;
ans.prefval = deltas[ind];
ans.suffval = deltas[ind];
ans.deltasum = deltas[ind];
return ans;
}
struct Node{
int s,e;
Data v;
Node *l, *r;
ll lazyval = 0;
bool doreplace = false;
Node(ll _s, ll _e){
s=_s;e=_e;
//cout<<s<<' '<<e<<'\n';
if (s==e){
v = init(s);
return;
}
int m = (s+e)/2;
l = new Node(s,m);
r = new Node(m+1,e);
v = combine(l->v, r->v);
}
void propagate(){
//cout<<"propagate "<<s<<' '<<e<<'\n';
//cout<<"lazy: "<<lazyval<<' '<<doreplace<<'\n';
if (doreplace){
v.prefval = lazyval;
v.suffval = lazyval;
v.deltasum = v.len * lazyval;
v.maxpref = v.len;
v.maxsuff = v.len;
v.maxlen = v.len;
} else {
v.prefval+=lazyval;
v.suffval+=lazyval;
v.deltasum+=v.len * lazyval;
}
if (s!=e){
if (doreplace){
l->doreplace = true;
l->lazyval = lazyval;
r->doreplace = true;
r->lazyval = lazyval;
} else {
l->lazyval+=lazyval;
r->lazyval+=lazyval;
}
}
lazyval=0;
doreplace=false;
}
Data query(ll a, ll b){
assert(a<=b);
assert(b<=n-2);
int m = (s+e)/2;
propagate();
if (a==s&&b==e){
return v;
}
if (b<=m){
return l->query(a,b);
} else if (m<a){
return r->query(a,b);
} else {
return combine(l->query(a,m),r->query(m+1,b));
}
}
void update(ll a, ll b, ll val, bool replace){
assert(b<=n-2);
int m = (s+e)/2;
//cout<<"update "<<a<<' '<<b<<' '<<val<<' '<<replace<<'\n';
if (a>b){return;}
if (a==s&&b==e){
if (replace){
doreplace=true;
lazyval=val;
} else {
lazyval+=val;
}
return;
}
propagate();
if (b<=m){
l->update(a,b,val,replace);
} else if (m<a){
r->update(a,b,val,replace);
} else {
l->update(a,m,val,replace);
r->update(m+1,b,val,replace);
}
l->propagate();
r->propagate();
v = combine(l->v,r->v);
}
};
ll x0;
Node *root;
void patch(ll l, ll r, ll s, ll c){
if (l==0){
x0+=s;
} else {
root->update(l-1,l-1,s,false);
}
root->update(l,r-1,c,false);
if (r!=n-1){
root->update(r,r,-s-(r-l)*c,false);
}
}
ll getDelta(ll ind){
Data dxl = root->query(ind,ind);
return dxl.deltasum;
}
ll getVal(ll ind){
if (ind==0){
return x0;
}
Data dxl = root->query(0,ind-1);
ll ans = x0+dxl.deltasum;
return ans;
}
void rewrite(ll l, ll r, ll s, ll c){
ll xlm1, xr1;
if (r!=n-1){
xr1 = getVal(r+1);
}
if (l==0){
x0=s;
} else {
ll xlm1 = getVal(l-1);
root->update(l-1,l-1,s-xlm1,true);
}
if (l<=r-1){
root->update(l,r-1,c,true);
}
if (r!=n-1){
root->update(r,r,xr1-s-(r-l)*c,true);
}
}
ll evaluate(ll l, ll r){
if (l==r){
return 1;
}
Data d = root->query(l,r-1);
return d.maxlen+1;
}
int main(){
//cin.tie(0);
//ios_base::sync_with_stdio(0);
ll q;
cin>>n>>q;
cin>>x0;
ll xprev = x0;
for (ll i = 1; i<n; i++){
ll xnew;
cin>>xnew;
deltas[i-1]=xnew-xprev;
xprev=xnew;
}
root = new Node(0,n-2);
/*for (ll i = 0; i<n-1; i++){
cout<<getDelta(i)<<' ';
}cout<<'\n';
for (ll i = 0; i<n; i++){
cout<<getVal(i)<<' ';
}cout<<'\n';*/
for (ll i = 0; i<q; i++){
ll t;
cin>>t;
ll l,r,s,c;
if (t==1){
cin>>l>>r>>s>>c;
patch(l-1,r-1,s,c);
/*for (ll i = 0; i<n-1; i++){
cout<<getDelta(i)<<' ';
}cout<<'\n';
for (ll i = 0; i<n; i++){
cout<<getVal(i)<<' ';
}cout<<'\n';*/
} else if (t==2){
cin>>l>>r>>s>>c;
rewrite(l-1,r-1,s,c);
/*for (ll i = 0; i<n-1; i++){
cout<<getDelta(i)<<' ';
}cout<<'\n';
for (ll i = 0; i<n; i++){
cout<<getVal(i)<<' ';
}cout<<'\n';*/
} else if (t==3){
cin>>l>>r;
cout<<evaluate(l-1,r-1)<<'\n';
} else {
continue;
}
}
}