#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int N = 2e5 + 3;
int n, q, a[N]; ll d[N];
struct node {
int L, R;
ll dp[2][2];
} st[N << 2];
node combine(node l, node r) {
node ans;
ans.L = l.L; ans.R = r.R;
ans.dp[0][0] = max({l.dp[0][0] + r.dp[0][0], l.dp[0][0] + r.dp[1][0], l.dp[0][1] + r.dp[0][0], (1LL * d[l.R] * d[r.L] >= 0) * (l.dp[0][1] + r.dp[1][0])});
ans.dp[0][1] = max({l.dp[0][0] + r.dp[0][1], l.dp[0][0] + r.dp[1][1], (1LL * d[l.R] * d[r.L] >= 0) * (l.dp[0][1] + r.dp[1][1])});
ans.dp[1][0] = max({l.dp[1][0] + r.dp[0][0], l.dp[1][0] + r.dp[1][0], (1LL * d[l.R] * d[r.L] >= 0) * (l.dp[1][1] + r.dp[1][0])});
ans.dp[1][1] = max({l.dp[1][0] + r.dp[0][1], l.dp[1][1] + r.dp[0][1], l.dp[1][0] + r.dp[1][1], (1LL * d[l.R] * d[r.L] >= 0) * (l.dp[1][1] + r.dp[1][1])});
return ans;
}
void build(int id, int l, int r) {
if (l == r) {
st[id].L = st[id].R = l;
st[id].dp[0][0] = 0;
st[id].dp[0][1] = 0;
st[id].dp[1][0] = 0;
st[id].dp[1][1] = abs(d[l]);
} else {
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = combine(st[id << 1], st[id << 1 | 1]);
}
}
void update(int id, int l, int r, int pos, int delta) {
if (l == r) {
d[l] += delta; //cout << d[l] << '\n';
st[id].dp[1][1] = abs(d[l]);
} else {
int mid = l + r >> 1;
if (pos <= mid) update(id << 1, l, mid, pos, delta);
else update(id << 1 | 1, mid + 1, r, pos, delta);
st[id] = combine(st[id << 1], st[id << 1 | 1]);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++) d[i] = a[i + 1] - a[i];
build(1, 1, n - 1);
while (q--) {
int l, r, x; cin >> l >> r >> x;
if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
cout << max({st[1].dp[0][0], st[1].dp[0][1], st[1].dp[1][0], st[1].dp[1][1]}) << '\n';
}
}
Compilation message
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int)':
Main.cpp:55:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:78:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
78 | if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
| ^~
Main.cpp:78:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
78 | if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
| ^~
Main.cpp:67:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:68:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
