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>
#define int long long
using namespace std;
int T[800100][2][2], arr[200100];
void merge(int n, int mid) {
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) {
T[n][i][j] = -1e18;
for (int k = 0; k < 2; k++)
for (int l = 0; l < 2; l++)
if (l != 1 || k != 1 || arr[mid] * arr[mid + 1] >= 0)
T[n][i][j] = max(T[n][i][j], T[n * 2][i][k] + T[n * 2 + 1][l][j]);
}
}
void upd(int p, int l, int r, int pos) {
if (l == r) {
T[p][1][1] = abs(arr[l]);
return;
}
int mid = l + r >> 1;
if (pos <= mid)
upd(p * 2, l, mid, pos);
else
upd(p * 2 + 1, mid + 1, r, pos);
merge(p, mid);
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = n; --i;)
arr[i + 1] -= arr[i], upd(1, 1, n, i + 1);
arr[1] = 0;
for (int i = 0; i < q; i++) {
int l, r, x;
cin >> l >> r >> x;
if (l != 1)
arr[l] += x, upd(1, 1, n, l);
if (r != n)
arr[r + 1] -= x, upd(1, 1, n, r + 1);
cout << max(max(T[1][0][0], T[1][0][1]), max(T[1][1][0], T[1][1][1])) << '\n';
}
}
Compilation message (stderr)
Main.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
Main.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid = l + r >> 1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |