#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int arr[N],a[N];
int n;
int sum[N][2][2];
void chmax(int &var,int v) {
if(v>var) var=v;
}
void pushup(int rt,bool mixable){
int i,j,_i,_j;
for(i=0;i<2;i++) {
for(j=0;j<2;j++) {
sum[rt][i][j]=0;
for(_i=0;_i<2;_i++) {
for(_j=0;_j<2;_j++) {
if(_i&&_j&&0==mixable) continue;
chmax(sum[rt][i][j],sum[rt<<1][i][_i]+sum[rt<<1|1][_j][j]);
}
}
}
}
}
void build(int l=1,int r=n,int rt=1) {
if(l==r) {
sum[rt][1][1]=abs(a[l]);
return ;
}
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt,a[m]*a[m+1]>=0);
}
void update(int x,int I,int l=1,int r=n,int rt=1) {
if(l==r) {
sum[rt][1][1]=abs(I);
return ;
}
int m=(l+r)>>1;
if(x<=m) update(x,I,l,m,rt<<1);
else update(x,I,m+1,r,rt<<1|1);
pushup(rt,a[m]*a[m+1]>=0);
}
int main() {
int q,i,l,r,x;
cin>>n>>q;
for(i=1;i<=n;i++) cin>>arr[i];
for(i=1;i<n;i++) a[i]=arr[i+1]-arr[i];
n--;
build();
int j,_i,_j,ans=0;
while(q--) {
cin>>l>>r>>x;
if(l-1>0) {
a[l-1]+=x;
update(l-1,a[l-1]);
}
if(r<=n) {
a[r]-=x;
update(r,a[r]);
}
ans=0;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
ans=max(ans,sum[1][i][j]);
cout<<ans<<endl;
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:52:8: warning: unused variable '_i' [-Wunused-variable]
52 | int j,_i,_j,ans=0;
| ^~
Main.cpp:52:11: warning: unused variable '_j' [-Wunused-variable]
52 | int j,_i,_j,ans=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
