#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define debug if(0)
const int mod = 1e9 + 7;
const ll infL = 1e18 + 7;
const int inf = 1e9 + 7;
void add(int &a, int b) { a = (a+b)%mod; }
int add(int a, int b, int c) { int res = (((a+b)%mod) + c)%mod; return res; }
#define T array<array<ll, 2>, 2>
struct segtree {
int size;
vector<T> seg;
vector<ll> v;
T ID;
void init(int n) {
ID[0][0] = ID[0][1] = ID[1][0] = ID[1][1] = 0;
size = 1;
while(size < n) size <<= 1;
seg.assign(2*size+2, ID);
v.assign(2*size+2, 0);
}
T comb(T a, T b, int pa, int pb) {
T res;
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
res[i][j] = max(a[i][0]+b[0][j], max(a[i][1]+b[0][j], a[i][0]+b[1][j]));
if(v[pa]*v[pb] < 0) res[i][j] = max(res[i][j], a[i][1]+b[1][j]);
}
}
return res;
}
void update(int i, ll val, int x, int lx, int rx) {
if(lx == rx) {
v[x] += val; seg[x][1][1] = abs(v[x]);
return;
}
int m = (lx+rx)/2;
if(i <= m) update(i, val, 2*x, lx, m);
else update(i, val, 2*x+1, m+1, rx);
seg[x] = comb(seg[2*x], seg[2*x+1], m, m+1);
}
void update(int i, ll val) { update(i, val, 1, 0, size-1); }
ll query() {
return max(max(seg[1][0][0], seg[1][1][0]), max(seg[1][0][1], seg[1][1][1]));
}
void print() {
for(int i=size; i<(2*size); i++) cerr<<v[i]<<" ";
cerr<<"\n";
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q; cin>>n>>q;
vector<int> x(n);
segtree st;
st.init(n+1);
for(int i=0; i<n; i++) {
cin>>x[i];
if(i) st.update(i, x[i]-x[i-1]);
}
int kt = 0;
while(q--) {
kt++;
int l, r; ll v; cin>>l>>r>>v; l--; r--;
// [l, r] -> d[l] = x[l] - x[l-1] = (x'[l] + d) - x[l-1] = (x'[l] - x[l-1]) + d -> diff d[l] increase by v
// [l, r] -> d[r+1] = x[r+1] - x[r] = x[r+1] - (x'[r] + d) = (x[r+1] - x'[r]) - d -> diff d[r+1] decrease by v
if(l) st.update(l, v);
if(r < (n-1)) st.update(r+1, -v);
debug {
if(kt == 2) {
st.print();
}
}
cout<<st.query()<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
