//chockolateman
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e9;
long long N,Q,a[200005],dp[200005],l_big[200005],l_small[200005];
struct Node
{
long long max_dp = -INF,val_max=-INF,val_min=-INF,lazy_max=0,lazy_min=0;
}st[800005];
void propagate(int v,int start,int end);
void update_max(int l,int r,long long val,int v = 1,int start = 1,int end = N)
{
if(start==l && end==r)
{
st[v].val_max = val + st[v].max_dp;
st[v].lazy_max = val;
return;
}
propagate(v,start,end);
int mid = (start + end)/2;
if(r <= mid)
update_max(l,r,val,2*v,start,mid);
else if(l > mid)
update_max(l,r,val,2*v+1,mid+1,end);
else
{
update_max(l,mid,val,2*v,start,mid);
update_max(mid+1,r,val,2*v+1,mid+1,end);
}
st[v].val_max = max(st[2*v].val_max,st[2*v+1].val_max);
}
void update_min(int l,int r,long long val,int v = 1,int start = 1,int end = N)
{
if(start==l && end==r)
{
st[v].val_min = st[v].max_dp - val;
st[v].lazy_min = val;
return;
}
propagate(v,start,end);
int mid = (start + end)/2;
if(r <= mid)
update_min(l,r,val,2*v,start,mid);
else if(l > mid)
update_min(l,r,val,2*v+1,mid+1,end);
else
{
update_min(l,mid,val,2*v,start,mid);
update_min(mid+1,r,val,2*v+1,mid+1,end);
}
st[v].val_min = max(st[2*v].val_min,st[2*v+1].val_min);
}
void propagate(int v,int start,int end)
{
int mid = (start + end)/2;
if(st[v].lazy_max)
{
update_max(start,mid,st[v].lazy_max,2*v,start,mid);
update_max(mid+1,end,st[v].lazy_max,2*v+1,mid+1,end);
st[v].lazy_max = 0;
}
if(st[v].lazy_min)
{
update_min(start,mid,st[v].lazy_min,2*v,start,mid);
update_min(mid+1,end,st[v].lazy_min,2*v+1,mid+1,end);
st[v].lazy_min = 0;
}
}
void update_dp(int pos,int v = 1,int start = 1,int end = N)
{
if(start==end)
{
st[v].max_dp = dp[pos-1];
st[v].val_max = dp[pos-1] + a[pos];
st[v].val_min = dp[pos-1] - a[pos];
return;
}
propagate(v,start,end);
int mid = (start + end)/2;
if(pos <= mid)
update_dp(pos,2*v,start,mid);
else
update_dp(pos,2*v+1,mid+1,end);
st[v].max_dp = max(st[2*v].max_dp,st[2*v+1].max_dp);
st[v].val_max = max(st[2*v].val_max,st[2*v+1].val_max);
st[v].val_min = max(st[2*v].val_min,st[2*v+1].val_min);
}
long long calc()
{
stack<pair<long long,int>> ord;
ord.push({-1e9,0});
for(int i = 1 ; i <= N ; i++)
{
while(ord.top().first > a[i])
ord.pop();
l_small[i] = ord.top().second+1;
ord.push({a[i],i});
}
while(!ord.empty())
ord.pop();
ord.push({1e9,0});
for(int i = 1 ; i <= N ; i++)
{
while(ord.top().first < a[i])
ord.pop();
l_big[i] = ord.top().second+1;
ord.push({a[i],i});
}
long long ret = 0;
for(int v = 1 ; v<= 4*N ; v++)
{
st[v].max_dp = -INF;
st[v].val_max=-INF;
st[v].val_min=-INF;
st[v].lazy_max=0;
st[v].lazy_min=0;
}
for(int i = 1 ; i <= N ; i++)
{
update_dp(i);
update_max(l_big[i],i,a[i]);
update_min(l_small[i],i,a[i]);
pair<long long,long long> res = {st[1].val_max,st[1].val_min};
dp[i] = max(res.first - a[i],res.second + a[i]);
}
return dp[N];
}
int main()
{
scanf("%lld%lld",&N,&Q);
for(int i = 1 ; i <= N ; i++)
scanf("%lld",&a[i]);
for(int l,r,x,i = 1 ; i <= Q ; i++)
{
scanf("%d%d%d",&l,&r,&x);
for(int j = l ; j <= r ; j++)
a[j] += x;
printf("%lld\n",calc());
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%lld%lld",&N,&Q);
| ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | scanf("%lld",&a[i]);
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | scanf("%d%d%d",&l,&r,&x);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |