#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll 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;
};
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{
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){
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 {
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){
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,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){
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;
}
}
}
Compilation message
Progression.cpp: In function 'void rewrite(ll, ll, ll, ll)':
Progression.cpp:176:8: warning: unused variable 'xlm1' [-Wunused-variable]
176 | ll xlm1, xr1;
| ^~~~
Progression.cpp:190:29: warning: 'xr1' may be used uninitialized in this function [-Wmaybe-uninitialized]
190 | root->update(r,r,xr1-s-(r-l)*c,true);
| ~~~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1129 ms |
59680 KB |
Output is correct |
| 2 |
Correct |
651 ms |
632 KB |
Output is correct |
| 3 |
Correct |
644 ms |
632 KB |
Output is correct |
| 4 |
Correct |
660 ms |
836 KB |
Output is correct |
| 5 |
Correct |
654 ms |
760 KB |
Output is correct |
| 6 |
Correct |
653 ms |
764 KB |
Output is correct |
| 7 |
Correct |
660 ms |
760 KB |
Output is correct |
| 8 |
Runtime error |
701 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
512 KB |
Output is correct |
| 2 |
Correct |
4 ms |
288 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
715 ms |
1048580 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1693 ms |
60260 KB |
Output is correct |
| 2 |
Correct |
974 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
994 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
967 ms |
1060 KB |
Output is correct |
| 5 |
Correct |
993 ms |
1160 KB |
Output is correct |
| 6 |
Correct |
1022 ms |
1052 KB |
Output is correct |
| 7 |
Correct |
1016 ms |
1272 KB |
Output is correct |
| 8 |
Runtime error |
680 ms |
1048580 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2095 ms |
59632 KB |
Output is correct |
| 2 |
Correct |
718 ms |
632 KB |
Output is correct |
| 3 |
Correct |
738 ms |
632 KB |
Output is correct |
| 4 |
Correct |
708 ms |
504 KB |
Output is correct |
| 5 |
Correct |
726 ms |
760 KB |
Output is correct |
| 6 |
Correct |
718 ms |
764 KB |
Output is correct |
| 7 |
Correct |
742 ms |
632 KB |
Output is correct |
| 8 |
Runtime error |
718 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1693 ms |
60260 KB |
Output is correct |
| 2 |
Correct |
974 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
994 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
967 ms |
1060 KB |
Output is correct |
| 5 |
Correct |
993 ms |
1160 KB |
Output is correct |
| 6 |
Correct |
1022 ms |
1052 KB |
Output is correct |
| 7 |
Correct |
1016 ms |
1272 KB |
Output is correct |
| 8 |
Runtime error |
680 ms |
1048580 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1129 ms |
59680 KB |
Output is correct |
| 2 |
Correct |
651 ms |
632 KB |
Output is correct |
| 3 |
Correct |
644 ms |
632 KB |
Output is correct |
| 4 |
Correct |
660 ms |
836 KB |
Output is correct |
| 5 |
Correct |
654 ms |
760 KB |
Output is correct |
| 6 |
Correct |
653 ms |
764 KB |
Output is correct |
| 7 |
Correct |
660 ms |
760 KB |
Output is correct |
| 8 |
Runtime error |
701 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
