This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 2e5 + 5;
struct Nod {
ll cap[2];
ll dp[2][2];
ll ans() {
return max(max(dp[0][0], dp[0][1]), max(dp[1][0], dp[1][1]));
}
} aint[4 * N];
int d[N];
Nod merge(const Nod& a, const Nod& b) {
Nod c = {{a.cap[0], b.cap[1]}, {{0, 0}, {0, 0}}};
for (int l = 0; l < 2; ++l)
for (int r = 0; r < 2; ++r)
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
if (i && j) {
if ((a.cap[1] > 0) == (b.cap[0] > 0))
c.dp[l][r] = max(c.dp[l][r], a.dp[l][i] + b.dp[j][r]);
} else {
c.dp[l][r] = max(c.dp[l][r], a.dp[l][i] + b.dp[j][r]);
}
return c;
}
void build(int p, int l, int r) {
if (l == r) {
aint[p] = {{d[l], d[r]}, {{0, 0}, {0, abs(d[r])}}};
return;
}
int m = (l + r) / 2;
build(p * 2, l, m);
build(p * 2 + 1, m + 1, r);
aint[p] = merge(aint[2 * p], aint[2 * p + 1]);
}
void upd(int p, int l, int r, int pos, int add) {
if (l == r) {
aint[p].cap[0] += add, aint[p].cap[1] += add;
aint[p].dp[1][1] = abs(aint[p].cap[0]);
return;
}
int m = (l + r) / 2;
if (pos <= m) upd(p * 2, l, m, pos, add);
else upd(p * 2 + 1, m + 1, r, pos, add);
aint[p] = merge(aint[p * 2], aint[p * 2 + 1]);
}
int main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n, q;
cin >> n >> q;
int a, b;
cin >> a;
for (int i = 1; i < n; ++i) {
cin >> b;
d[i] = b - a;
a = b;
}
build(1, 1, n - 1);
while (q--) {
int l, r, add;
cin >> l >> r >> add;
if (l - 1 > 0)
upd(1, 1, n - 1, l - 1, add);
if (r < n)
upd(1, 1, n - 1, r, -add);
cout << aint[1].ans() << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |