#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll deltas[300000];
struct Data{
ll len = 1;
ll maxpref=1;
ll maxsuff=1;
ll prefval=0;
ll suffval=0;
ll maxlen=1;
ll deltasum = 0;
};
Data combine(const Data &l, const 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{
ll s,e,m;
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;
}
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);
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 {
Data dl = l->query(a,m);
Data dr = r->query(m+1,b);
//cout<<"combine "<<a<<' '<<m<<' '<<dl.deltasum<<'\n';
//cout<<"combine "<<m+1<<' '<<b<<' '<<dr.deltasum<<'\n';
Data c = combine(dl,dr);
//cout<<"ans: "<<c.deltasum<<'\n';
return c;
}
}
void update(ll a, ll b, ll val, bool replace){
//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,n;
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){
if (l==0){
x0=s;
} else {
ll xlm1 = getVal(l-1);
root->update(l-1,l-1,s-xlm1,true);
}
root->update(l,r-1,c,true);
if (r!=n-1){
ll xr1 = getVal(r+1);
root->update(r,r,xr1-s-(r-l)*c,true);
}
}
ll evaluate(ll l, ll r){
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++){
ll d = getDelta(i);
cout<<"d at "<<i<<": "<<d<<'\n';
}
for (ll i = 0; i<n; i++){
ll v = getVal(i);
cout<<"v at "<<i<<": "<<v<<'\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);
} else if (t==2){
cin>>l>>r>>s>>c;
rewrite(l-1,r-1,s,c);
} else if (t==3){
cin>>l>>r;
cout<<evaluate(l-1,r-1)<<'\n';
} else {
continue;
}
/*for (ll i = 0; i<n-1; i++){
ll d = getDelta(i);
cout<<"d at "<<i<<": "<<d<<'\n';
}
for (ll i = 0; i<n; i++){
ll v = getVal(i);
cout<<"v at "<<i<<": "<<v<<'\n';
}*/
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
221 ms |
78456 KB |
Output is correct |
| 2 |
Correct |
97 ms |
632 KB |
Output is correct |
| 3 |
Correct |
93 ms |
704 KB |
Output is correct |
| 4 |
Correct |
93 ms |
632 KB |
Output is correct |
| 5 |
Correct |
93 ms |
760 KB |
Output is correct |
| 6 |
Correct |
96 ms |
760 KB |
Output is correct |
| 7 |
Correct |
93 ms |
664 KB |
Output is correct |
| 8 |
Runtime error |
658 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1024 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
203 ms |
157604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
203 ms |
157744 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
203 ms |
157604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
221 ms |
78456 KB |
Output is correct |
| 2 |
Correct |
97 ms |
632 KB |
Output is correct |
| 3 |
Correct |
93 ms |
704 KB |
Output is correct |
| 4 |
Correct |
93 ms |
632 KB |
Output is correct |
| 5 |
Correct |
93 ms |
760 KB |
Output is correct |
| 6 |
Correct |
96 ms |
760 KB |
Output is correct |
| 7 |
Correct |
93 ms |
664 KB |
Output is correct |
| 8 |
Runtime error |
658 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
