#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<pii,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=2*1e5+1,mx=1e6;
#define int long long
struct node{
int dp[2][2],l,r;
// left right border
};
node seg[2*mxn+10];
int v[mxn+10],d[mxn+10];
int n,q;
node merg(node a,node b){
node ans;
if(a.l==INT_MAX)return b;
else if(b.l==INT_MAX)return a;
ans.l=a.l;
ans.r=b.r;
ans.dp[0][1]=max({a.dp[0][1]+b.dp[0][1],a.dp[0][0]+b.dp[1][1],a.dp[0][0]+b.dp[0][1]});
ans.dp[0][0]=max({a.dp[0][0]+b.dp[1][0],a.dp[0][1]+b.dp[0][0],a.dp[0][0]+b.dp[0][0]});
ans.dp[1][0]=max({a.dp[1][0]+b.dp[1][0],a.dp[1][1]+b.dp[0][0],a.dp[1][0]+b.dp[0][0]});
ans.dp[1][1]=max({a.dp[1][1]+b.dp[0][1],a.dp[1][0]+b.dp[1][1],a.dp[1][0]+b.dp[0][1]});
if((d[a.r]>=0&&d[b.l]>=0)||(d[a.r]<=0&&d[b.l]<=0)){
ans.dp[0][1]=max(ans.dp[0][1],a.dp[0][1]+b.dp[1][1]);
ans.dp[0][0]=max(ans.dp[0][0],a.dp[0][1]+b.dp[1][0]);
ans.dp[1][0]=max(ans.dp[1][0],a.dp[1][1]+b.dp[1][0]);
ans.dp[1][1]=max(ans.dp[1][1],a.dp[1][1]+b.dp[1][1]);
}
//0 take left/right
return ans;
}
void init(node&a){a.l=a.r=INT_MAX,a.dp[0][1]=a.dp[1][0]=a.dp[1][1]=a.dp[0][0]=0;}
void up(int pos,int val){
pos+=n;
seg[pos].l=pos-n;
seg[pos].r=pos-n;
seg[pos].dp[1][1]=val;
for(;pos>1;pos>>=1){
node a=seg[pos],b=seg[pos^1];
if(pos&1)swap(a,b);
seg[pos>>1]=merg(a,b);
}
}
int qry(int l,int r){
node ansl,ansr;
init(ansl);
init(ansr);
for(l+=n,r+=n;l<=r;l>>=r,r>>=1){
if(l&1)ansl=merg(ansl,seg[l++]);
if(!(r&1))ansr=merg(seg[r--],ansr);
}
ansl=merg(ansl,ansr);
return max({ansl.dp[0][0],ansl.dp[0][1],ansl.dp[1][1],ansl.dp[1][0]});
}
int32_t main(){
cin>>n>>q;
for(int i=0;i<2*n;i++)init(seg[i]);
for(int i=0;i<n;i++)cin>>v[i];
n--;
for(int i=0;i<n;i++)d[i]=v[i+1]-v[i];
for(int i=0;i<n;i++)up(i,abs(d[i]));
while(q--){
int l,r,x;cin>>l>>r>>x;
l--,r--;
if(l)d[l-1]+=x;
if(r<n)d[r]-=x;
if(l)up(l-1,abs(d[l-1]));
if(r<n)up(r,abs(d[r]));//2 0 2 2
cout<<qry(0,n)<<'\n';
}
}
| # |
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 |
- |
