#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
using i64 = std::int64_t;
constexpr i64 inf = std::numeric_limits<i64>::max() / 3;
struct Segtree {
int size, logn;
vector<array<array<i64, 3>, 3>> data;
vector<i64> lazy;
explicit Segtree(const vector<int>& vec) {
const int n = vec.size();
while ((1 << logn) < n) {
logn += 1;
}
size = 1 << logn;
data.resize(2 * size);
lazy.resize(size);
for (int i = 0; i < n; ++i) {
auto& a = data[i + size];
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
a[j][k] = -inf;
}
}
a[0][0] = 0;
a[0][1] = a[1][0] = vec[i];
a[0][2] = a[2][0] = -vec[i];
}
for (int i = size - 1; i > 0; --i) {
fetch(i);
}
}
void fetch(const int k) {
auto& a = data[k];
auto& l = data[2 * k];
auto& r = data[2 * k + 1];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
a[i][j] = -inf;
a[i][j] = std::max(a[i][j], l[i][0] + r[0][j]);
a[i][j] = std::max(a[i][j], l[i][1] + r[2][j]);
a[i][j] = std::max(a[i][j], l[i][2] + r[1][j]);
}
}
}
void apply(const int k, const i64 e) {
auto& a = data[k];
a[0][1] += e;
a[1][0] += e;
a[0][2] -= e;
a[2][0] -= e;
a[1][1] += 2 * e;
a[2][2] -= 2 * e;
if (k < size) {
lazy[k] += e;
}
}
void flush(const int k) {
if (lazy[k] != 0) {
apply(2 * k, lazy[k]);
apply(2 * k + 1, lazy[k]);
lazy[k] = 0;
}
}
void push(const int k) {
const int lsb = __builtin_ctz(k);
for (int d = logn; d > lsb; --d) {
flush(k >> d);
}
}
void pull(int k) {
k >>= __builtin_ctz(k);
while (k > 1) {
fetch(k >>= 1);
}
}
void operate(int l, int r, const int x) {
l += size, r += size;
push(l), push(r);
const int lc = l, rc = r;
while (l < r) {
if (l & 1) apply(l++, x);
if (r & 1) apply(--r, x);
l >>= 1, r >>= 1;
}
pull(lc), pull(rc);
}
i64 fold() const {
return data[1][0][0];
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, Q;
std::cin >> N >> Q;
vector<int> A(N);
for (auto& x : A) {
std::cin >> x;
}
Segtree seg(A);
while (Q--) {
int l, r, x;
std::cin >> l >> r >> x;
seg.operate(l - 1, r, x);
std::cout << seg.fold() << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
