#include <bits/stdc++.h>
using namespace std;
void fast() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
long long a = rand();
long long b = rand();
return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
freopen("problem.in", "r", stdin);
freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
// #define endl '\n'
// #define double long double
#define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;
int n, q;
const int MXN = 200005;
int arr[MXN];
int df[MXN];
struct info {
int with[2][2] = {{0}}; // first and last, taken or not taken
info() {
with[0][0] = with[0][1] = with[1][0] = with[1][1] = 0;
}
} seg[MXN * 4];
info get(int x) {
info res;
res.with[1][1] = abs(x);
return res;
}
int sg(int x) {
if (x > 0) return 1;
if (x < 0) return -1;
return 0;
}
info comb(info l, info r, int m) {
info res;
if (sg(df[m]) == sg(df[m+1]) || df[m] == 0 || df[m+1] == 0) {
for (int L=0; L<2; L++) {
for (int R=0; R<2; R++) {
for (int k=0; k<2; k++) for (int m=0; m<2; m++) {
res.with[L][R] = max(res.with[L][R], l.with[L][k] + r.with[m][R]);
}
}
}
}
else {
for (int L=0; L<2; L++) {
for (int R=0; R<2; R++) {
for (int k=0; k<2; k++) for (int m=0; m<2; m++) {
if (k && m) continue;
else res.with[L][R] = max(res.with[L][R], l.with[L][k] + r.with[m][R]);
}
}
}
}
return res;
}
void build(int ind, int l, int r) {
if (l == r) {
seg[ind] = get(df[l]);
return;
}
int m = (l + r) / 2;
build(ind*2, l, m);
build(ind*2+1, m+1, r);
seg[ind] = comb(seg[ind*2], seg[ind*2+1], m);
}
void update(int ind, int l, int r, int pos) {
if (l == r) {
seg[ind] = get(df[l]);
return;
}
int m = (l + r) / 2;
if (pos <= m) update(ind*2, l, m, pos);
else update(ind*2+1, m+1, r, pos);
seg[ind] = comb(seg[ind*2], seg[ind*2+1], m);
}
int best() {
int a = 0;
for (int i=0; i<2; i++) for (int j=0; j<2; j++) a = max(a, seg[1].with[i][j]);
return a;
}
signed main() {
ran(); fast();
cin >> n >> q;
for (int i=1; i<=n; i++) cin >> arr[i];
if (n == 1) {
for (int i=0; i<q; i++) cout << 0 << endl;
exit(0);
}
for (int i=1; i<n; i++) df[i] = arr[i+1] - arr[i];
build(1, 1, n-1);
while (q--) {
int l, r, k;
cin >> l >> r >> k;
if (l > 1) {
df[l-1] += k;
update(1, 1, n, l-1);
}
if (r < n) {
df[r] -= k;
update(1, 1, n, r);
}
cout << best() << endl;
}
}
Compilation message
Main.cpp: In function 'void usaco()':
Main.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen("problem.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen("problem.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
25292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
25292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
25292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
