#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,tree[4*N][2][2],a[N],x[N],n,q;
void update(int u,int ind,int l,int r,int val) {
if(l>ind || r<ind) return;
if(l==r) {
tree[u][0][0] = 0;
tree[u][1][1] = abs(val);
return;
}
int mid = (l+r)/2;
update(2*u,ind,l,mid,val);
update(2*u+1,ind,mid+1,r,val);
for(int i=0;i<2;i++) {
for(int j=0;j<2;j++){ tree[u][i][j] = 0;
for(int k=0;k<2;k++) {
for(int c=0;c<2;c++) {
if(k==1 && c==1 && x[mid]*x[mid+1]<0) continue;
tree[u][i][j] = max(tree[2*u][i][k] + tree[2*u+1][c][j], tree[u][i][j]);
}
}
}
}
}
main(){
cin>>n>>q;
for(int i=1;i<=n;i++) {
cin >> a[i];
if(i-1) update(1,i,1,n,a[i]-a[i-1]);
x[i] = a[i] - a[i-1];
}
while(q--) {
int l,r,val;
cin>>l>>r>>val;
x[l] += val;
x[r+1] += -val;
if(l-1) update(1,l,1,n,x[l]);
update(1,r+1,1,n,x[r+1]);
cout<<max(max(tree[1][1][1],tree[1][0][0]),max(tree[1][1][0],tree[1][0][1]))<<"\n";
}
}
Compilation message
Main.cpp:29:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
29 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
