// source problem :
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
const int inf = 1e18;
void ckmax(int& f, int s)
{
f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
f = (f < s ? f : s);
}
struct info {
int tf, tb, a[2][2];
info() {
tf = -1;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) a[i][j] = -inf;
}
}
info (int x) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) a[i][j] = -inf;
}
if (x == 0) {
tf = tb = 0;
a[1][1] = 0;
}
if (x < 0) {
tf = tb = 1;
a[1][1] =-x;
}
if (x > 0) {
tf = tb = 2;
a[1][1] = x;
}
a[0][0] = 0;
}
int get() {
return max({0LL, a[0][0], a[0][1], a[1][0], a[1][1]});
}
void to_string() {
cout << "DATA " << tf << ' ' << tf << ' ' << a[0][0] << ' ' << a[0][1] << ' ' << a[1][0] << ' ' << a[1][1] << '\n';
}
};
info operator+(info a, info b) {
if (a.tf < 0) return b;
if (b.tf < 0) return a;
//a.to_string();
//b.to_string();
info res;
res.tf = a.tf;
res.tb = b.tb;
//res.to_string();
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
ckmax(res.a[i][j], a.a[i][j]);
ckmax(res.a[i][j], b.a[i][j]);
for (int c = 0; c < 2; c++) for (int d = 0; d < 2; d++) {
if (a.a[i][j] < 0 || b.a[c][d] < 0) continue;
if (j && c) {
if ((a.tb == 1 && b.tf == 2) || (a.tb == 2 && b.tf == 1)) continue;
ckmax(res.a[i][d], a.a[i][j] + b.a[c][d]);
}
else {
ckmax(res.a[i][d], a.a[i][j] + b.a[c][d]);
}
}
}
// res.to_string();
// cout << '\n';
return res;
}
info st[1 << 19];
void update(int pos, int x, int id = 1, int l = 1, int r = 1 << 18) {
if (l == r) {
st[id] = info(x);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(pos, x, id << 1, l, mid);
else update(pos, x, id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = n; i > 1; i--) {
a[i] -= a[i - 1];
update(i, a[i]);
}
while (q--) {
int l, r, x;
cin >> l >> r >> x;
if (l > 1) {
a[l] += x;
update(l, a[l]);
}
if (r < n) {
a[r + 1] -= x;
update(r + 1, a[r + 1]);
}
cout << st[1].get() << '\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... |