#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
const int nax = 200'000 + 10;
const ll INF = 1e18;
int n, q;
ll val[(1 << 18)];
struct Node {
ll f[2][2];
int l, r;
};
Node T[(1 << 19)];
int R;
Node combine(Node &a, Node &b) {
Node c;
for(int l : {0,1}) for(int r : {0,1}) c.f[l][r] = 0;
for(int l : {0,1}) {
for(int r : {0,1}) {
for(int l1 : {0,1}) {
for(int r1 : {0,1}) {
if(l1 + r1 == 2 && (ll)val[a.r] * val[b.r] < 0) continue;
c.f[l][r] = max(c.f[l][r], a.f[l][l1] + b.f[r1][r]);
}
}
}
}
return c;
}
void upd(int a, ll x) {
a += R;
for(int l : {0,1}) {
for(int r : {0,1}) {
if(l != r) T[a].f[l][r] = -INF;
else if(r) T[a].f[l][r] = abs(x);
else T[a].f[l][r] = 0;
}
}
while(a > 1) {
a /= 2;
T[a] = combine(T[2*a], T[2*a+1]);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 0; i < n; ++i) {
cin >> val[i];
}
for(int i = 0; i < n - 1; ++i) {
val[i] -= val[i + 1];
}
val[n - 1] = 0;
R = 1;
while(R < n) R *= 2;
for(int i = R; i < R * 2; ++i) {
T[i].l = T[i].r = i - R;
}
for(int i = 0; i < R; ++i) {
upd(i, val[i]);
}
while(q--) {
int l, r, x;
cin >> l >> r >> x;
l-=2;
if(l >= 0) {
val[l] -= x;
upd(l, val[l]);
}
r--;
if(r < n - 1) {
val[r] += x;
upd(r, val[r]);
}
ll ans = 0;
for(int a : {0,1}) for(int b : {0,1}) ans = max(ans, T[1].f[a][b]);
cout << ans << "\n";
}
}
| # |
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 |
- |
