#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int N = 2e5 + 100;
struct st {
ll a[3][3];
// 0 - neg, 1 - none, 2 - pos
// left, right
st() {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
a[i][j] = -inf;
}
}
}
st(ll x) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
a[i][j] = -inf;
}}
a[1][1] = 0;
a[0][1] = -x;
a[1][0] = -x;
a[2][1] = x;
a[1][2] = x;
}
} t[4 * N];
inline st mg(const st &a, const st &b) {
st res;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int z = 0; z < 3; ++z) {
for (int k = 0; k < 3; ++k) {
if (j + z == 2) chmax(res.a[i][k], a.a[i][j] + b.a[z][k]);
}}
}} return res;
}
ll p[4 * N];
int a[N];
inline void build(int v, int vl, int vr) {
if (vl == vr) return void(t[v] = st(a[vl]));
int m = vl + vr >> 1;
build(2 * v + 1, vl, m);
build(2 * v + 2, m + 1, vr);
t[v] = mg(t[2 * v + 1], t[2 * v + 2]);
}
inline void push(int v) {
if (!p[v]) return;
for (int u : {2 * v + 1, 2 * v + 2}) {
p[u] += p[v];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
ll to_add = 0;
to_add += (i == 0 ? -p[v] : (i == 1 ? 0 : p[v]));
to_add += (j == 0 ? -p[v] : (j == 1 ? 0 : p[v]));
t[u].a[i][j] += to_add;
}}
}
p[v] = 0;
}
inline void upd(int v, int vl, int vr, int l, int r, int x) {
if (l > r) return;
else if (vl == l && vr == r) {
p[v] += x;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
ll to_add = 0;
to_add += (i == 0 ? -x : (i == 1 ? 0 : x));
to_add += (j == 0 ? -x : (j == 1 ? 0 : x));
t[v].a[i][j] += to_add;
}}
return;
}
push(v);
int m = vl + vr >> 1;
upd(2 * v + 1, vl, m, l, min(r, m), x);
upd(2 * v + 2, m + 1, vr, max(l, m + 1), r, x);
t[v] = mg(t[2 * v + 1], t[2 * v + 2]);
}
inline void solve() {
int n, q;
cin >> n >> q;
for (int i = 0; i < n; ++i) cin >> a[i];
build(0, 0, n - 1);
while (q--) {
int l, r, x;
cin >> l >> r >> x;
upd(0, 0, n - 1, --l, --r, x);
cout << t[0].a[1][1] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
Compilation message
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:63:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int m = vl + vr >> 1;
| ~~~^~~~
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:97:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
97 | int m = vl + vr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
56660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
56660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
56660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
