#include "bits/stdc++.h"
using namespace std;
struct Node {
long long mx;
long long mxl;
long long mxr;
long long mxlr;
int l;
int r;
};
template <class T, int N>
struct Seg {
static_assert(__builtin_popcount(N) == 1);
const T ID = {0, 0, 0, 0, 0, 0};
T cmb(T a, T b) {
Node n;
n.mx = max(a.mxr + b.mx, a.mx + b.mxl);
n.mxl = max(a.mxl + max(b.mxl, b.mx), a.mxlr + b.mx);
n.mxr = max(max(a.mxr, a.mx) + b.mxr, a.mx + b.mxlr);
n.mxlr = max(a.mxlr + max(b.mxr, b.mx), max(a.mxl, a.mx) + b.mxlr);
n.l = a.l;
n.r = b.r;
if (a.r == b.l) {
n.mx = max(n.mx, a.mxr + b.mxl);
n.mxl = max(n.mxl, a.mxlr + b.mxl);
n.mxr = max(n.mxr, a.mxr + b.mxlr);
n.mxlr = max(n.mxlr, a.mxlr + b.mxlr);
}
return n;
}
T seg[2 * N];
Seg() {
for (int i = 0; i < 2 * N; i++)
seg[i] = ID;
}
void pull(int p) { seg[p] = cmb(seg[2 * p], seg[2 * p + 1]); }
void print() {
for (int i = N; i < 2 * N; i++) cout << seg[i].mxlr << ' ' << seg[i].l << '\n';
}
void build(vector<T> &v, int p = 1, int L = 0, int R = N - 1) {
if (L == R) {
if (size(v) > L)
seg[p] = v[L];
} else {
int M = (L + R) / 2;
build(v, 2 * p, L, M);
build(v, 2 * p + 1, M + 1, R);
pull(p);
}
}
void upd(int v, long long val, int p = 1, int L = 0, int R = N - 1) {
if (L == R) {
seg[p].mxlr *= seg[p].l;
seg[p].mxlr += val;
if (seg[p].mxlr < 0)
seg[p].l = seg[p].r = -1;
if (seg[p].mxlr > 0)
seg[p].l = seg[p].r = 1;
seg[p].mxlr = abs(seg[p].mxlr);
} else {
int M = (L + R) / 2;
if (v <= M)
upd(v, val, 2 * p, L, M);
else
upd(v, val, 2 * p + 1, M + 1, R);
pull(p);
}
}
T query(int lo, int hi, int p = 1, int L = 0, int R = N - 1) {
if (lo > R || L > hi) return ID;
if (lo <= L && R <= hi) return seg[p];
int M = (L + R) / 2;
return cmb(query(lo, hi, 2 * p, L, M), query(lo, hi, 2 * p + 1, M + 1, R));
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<Node> diff(n - 1);
for (int i = 0; i < n - 1; i++) {
int mult = 1;
if (v[i + 1] < v[i]) mult = -1;
diff[i] = {0, 0, 0, abs(v[i + 1] - v[i]), mult, mult};
}
Seg<Node, 8> seg;
seg.build(diff);
while (q--) {
int l, r, x;
cin >> l >> r >> x;
l--, r--;
if (l != 0) seg.upd(l - 1, x);
if (r != n - 1) seg.upd(r, -x);
cout << seg.query(0, n).mxlr << '\n';
}
}
Compilation message
Main.cpp: In instantiation of 'void Seg<T, N>::build(std::vector<_Tp>&, int, int, int) [with T = Node; int N = 8]':
Main.cpp:97:16: required from here
Main.cpp:44:16: warning: comparison of integer expressions of different signedness: 'std::vector<Node>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if (size(v) > L)
| ~~~~~~~~^~~
| # |
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 |
- |
