#include <bits/stdc++.h>
#define vec vector
#define f first
#define s second
#define endl '\n'
#define pb push_back
#define sz(x) (int)x.size()
#define umax(a,b) a=max(a,b)
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const ll inf=1e18;
const int N=2e5+1;
pii to[2][2][2][2];
struct tr{
ll dp[2][2];
tr(){
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
dp[i][j]=0;
}
}
}
};
tr emp,t[4*N];
tr mg(const tr&a,const tr &b){
tr c;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
for(int t=0;t<2;t++){
if(to[i][j][t][k].f!=-1){
pii w=to[i][j][t][k];
umax(c.dp[w.f][w.s],a.dp[i][j]+b.dp[t][k]);
}
}
}
}
}
return c;
}
void upd(int id,ll x,int v,int l,int r){
if(l==r){
tr c;
int ty=(x<0?0:1);
c.dp[ty][ty]=abs(x);
c.dp[ty^1][ty^1]=0;
t[v]=c;
return;
}
int m=(l+r)>>1;
if(m>=id) upd(id,x,2*v,l,m);
else upd(id,x,2*v+1,m+1,r);
t[v]=mg(t[2*v],t[2*v+1]);
}
ll b[N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
for(int t=0;t<2;t++){
to[i][j][k][t]={-1,-1};
}
}
emp.dp[i][j]=0;
}
}
to[0][1][1][1]={0,1};
//to[0][0][1][1]={0,1};
to[0][0][0][1]={0,1};
to[1][1][1][1]={1,1};
to[0][0][0][0]={0,0};
to[1][0][0][0]={1,0};
// to[1][1][0][0]={1,0};
to[1][1][1][0]={1,0};
int n,q;
cin>>n>>q;
vec<int>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
// upd(1,0,1,2,n);
for(int i=2;i<=n;i++){
b[i]=a[i]-a[i-1];
upd(i,b[i],1,2,n);
}
while(q--){
int l,r,x;
cin>>l>>r>>x;
if(r+1<=n){
b[r+1]-=x;
upd(r+1,b[r+1],1,2,n);
}
if(l!=1){
b[l]+=x;
upd(l,b[l],1,2,n);
}
tr c=t[1];
ll mx=-inf;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
umax(mx,c.dp[i][j]);
}
}
cout<<mx<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
25292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
25292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
25292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
