#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define left (node<<1),l,(l+r)>>1
#define right ((node<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 200005;
ll sgt[4*N][5][5],a[N],b[N];
ll get1(int node,ll x,ll y){
ll p = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][1][1];
ll q = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][0][1];
ll z = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][0][1];
ll d = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][1][1];
if(x*y < 0) d=0;
return max(max(p,q),max(z,d));
}
ll get2(int node,ll x, ll y){
ll p = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][0][0];
ll q = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][1][0];
ll z = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][0][0];
ll d = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][1][0];
if (x*y < 0) d=0;
return max(max(p,q),max(z,d));
}
ll get3(int node,ll x,ll y){
ll p = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][1][1];
ll q = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][0][1];
ll z = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][0][1];
ll d = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][1][1];
if(x*y < 0) d=0;
return max(max(p,q),max(z,d));
}
ll get4(int node,ll x,ll y){
ll p = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][1][0];
ll q = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][0][0];
ll z = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][0][0];
ll d = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][1][0];
if (x*y < 0) d=0;
return max(max(p,q),max(z,d));
}
void build(int node,int l,int r){
if (l == r){
sgt[node][1][1] = abs(b[l]);
sgt[node][1][0] = sgt[node][0][1]= sgt[node][0][0] = 0;
sgt[node][2][0] = sgt[node][0][2] = b[l];
return;
}
build(left),build(right);
ll x = sgt[(node<<1)][0][2],y = sgt[((node<<1)|1)][2][0];
sgt[node][1][1] = get1(node,x,y);
sgt[node][1][0] = get2(node,x,y);
sgt[node][0][1] = get3(node,x,y);
sgt[node][0][0] = get4(node,x,y);
sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
sgt[node][2][0] = sgt[(node<<1)][2][0];
sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
sgt[node][2][0] = sgt[(node<<1)][2][0];
}
void upd(int node,int l,int r,int ind){
if (l == r){
sgt[node][1][1] = abs(b[l]);
sgt[node][1][0] = sgt[node][0][1]= sgt[node][0][0] = 0;
sgt[node][2][0] = sgt[node][0][2] = b[l];
return;
}
if (ind > ((l+r)>>1)) upd(right,ind);
else upd(left,ind);
ll x = sgt[(node<<1)][0][2],y = sgt[((node<<1)|1)][2][0];
sgt[node][1][1] = get1(node,x,y);
sgt[node][1][0] = get2(node,x,y);
sgt[node][0][1] = get3(node,x,y);
sgt[node][0][0] = get4(node,x,y);
sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
sgt[node][2][0] = sgt[(node<<1)][2][0];
}
main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n,q;
cin>>n>>q;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<n;i++)
b[i] = a[i]-a[i+1];
build(1,1,n-1);
while(q--){
int l,r,k;
cin>>l>>r>>k;
if (l > 1) b[l-1]-=k,upd(1,1,n-1,l-1);
if (r < n) b[r]+=k,upd(1,1,n-1,r);
ll x = max(max(sgt[1][1][1],sgt[1][0][0]),max(sgt[1][1][0],sgt[1][0][1]));
cout<<x<<"\n";
}
}
Compilation message
Main.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
88 | main (){
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
6 ms |
2028 KB |
Output is correct |
8 |
Correct |
7 ms |
2000 KB |
Output is correct |
9 |
Correct |
6 ms |
1996 KB |
Output is correct |
10 |
Correct |
8 ms |
1996 KB |
Output is correct |
11 |
Correct |
6 ms |
1980 KB |
Output is correct |
12 |
Correct |
7 ms |
2044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
6 ms |
2028 KB |
Output is correct |
8 |
Correct |
7 ms |
2000 KB |
Output is correct |
9 |
Correct |
6 ms |
1996 KB |
Output is correct |
10 |
Correct |
8 ms |
1996 KB |
Output is correct |
11 |
Correct |
6 ms |
1980 KB |
Output is correct |
12 |
Correct |
7 ms |
2044 KB |
Output is correct |
13 |
Correct |
722 ms |
113048 KB |
Output is correct |
14 |
Correct |
705 ms |
115096 KB |
Output is correct |
15 |
Correct |
704 ms |
115240 KB |
Output is correct |
16 |
Correct |
739 ms |
115212 KB |
Output is correct |
17 |
Correct |
709 ms |
114952 KB |
Output is correct |
18 |
Correct |
718 ms |
115860 KB |
Output is correct |