#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const int maxn = 2e5+10;
int n,q;
ll a[maxn];
//00
//01
//10
//11
ll sgn(ll x) {
if (x==0) return 0;
if (x>0) return 1;
if (x<0) return -1;
assert(false);
return 1;
}
struct node {
ll dx;
map<pair<int,int>,ll> dp;
node() {
dx = 0;
dp[{sgn(0),sgn(0)}] = abs(0);
}
node(ll x) {
dx = x;
dp[{sgn(0),sgn(0)}] = abs(0);
dp[{sgn(x),sgn(x)}] = abs(x);
}
};
bool mergable(pair<int,int> p, pair<int,int> q) {
return p.second*q.first >= 0;
}
node merge(node x, node y) {
node res = x;
for (auto p: y.dp) {
res.dp[p.first] = max(res.dp[p.first], p.second);
}
for (auto p: x.dp) {
for (auto q: y.dp) {
if (mergable(p.first,q.first)) {
pair<int,int> ends = {p.first.first,q.first.second};
res.dp[ends] = max(res.dp[ends], p.second+q.second);
}
}
}
return res;
}
node t[4*maxn];
void upd(int v, int tl, int tr, int i, ll dx) {
if (tl==tr) {
ll prev = t[v].dx;
t[v] = node(prev+dx);
} else {
int tm=(tl+tr)/2;
if (i<=tm) {
upd(2*v,tl,tm,i,dx);
} else {
upd(2*v+1,tm+1,tr,i,dx);
}
t[v]=merge(t[2*v],t[2*v+1]);
}
}
void build(int v, int tl, int tr) {
if (tl==tr) {
if (tl>1) {
t[v]=node(a[tl]-a[tl-1]);
} else {
t[v]=node();
}
} else {
int tm = (tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=merge(t[2*v],t[2*v+1]);
}
}
node qry(int v, int tl, int tr, int l, int r) {
assert(0);
if (l>tr || r<tl) {
return node();
} else if (l<=tl && tr<=r) {
return t[v];
} else {
int tm = (tl+tr)/2;
return merge(qry(2*v,tl,tm,l,r),qry(2*v+1,tm+1,tr,l,r));
}
}
void update(int l, int r, ll dx) {
if (l+1==r) {
if (l>1) {
upd(1,1,n,l,dx);
}
if (r<n) {
upd(1,1,n,r+1,-dx);
}
} else {
for (int idx: set<int>{l,r}) {
if (idx>1) {
upd(1,1,n,idx,dx);
}
if (idx<n) {
upd(1,1,n,idx+1,-dx);
}
}
}
}
ll solve() {
ll res = 0;
for (auto p: t[1].dp) {
res = max(res, p.second);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>q;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
build(1,1,n);
while (q--) {
int l,r,dx;
cin>>l>>r>>dx;
update(l,r,dx);
cout<<solve()<<"\n";
}
return 0;
}
/*
ll solve() {
ll dp0 = 0;
ll dp1 = 0;
ll diff0 = 0;
for (int i=2; i<=n; i++) {
ll diff = a[i]-a[i-1];
if (diff0*diff>=0) {
ll _dp0 = max(dp0,dp1);
ll _dp1 = max(dp1,dp0)+abs(diff);
dp0 = _dp0;
dp1 = _dp1;
} else {
ll _dp0 = max(dp0,dp1);
ll _dp1 = dp0+abs(diff);
dp0 = _dp0;
dp1 = _dp1;
}
diff0 = diff;
}
return max(dp0, dp1);
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
94316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
94316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
94316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
