#include "bits/stdc++.h"
#include <cstring>
#include <fstream>
using namespace std;
#define ll long long
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define open(s) freopen(((string) s + ".in").c_str(), "r", stdin); freopen(((string) s + ".out").c_str(), "w", stdout)
#define all(i) i.begin(), i.end()
#define boost() cin.sync_with_stdio(0); cin.tie()
#define int ll
int sign(int g){
return g == 0 ? 0 : g > 0 ? 1 : -1;
}
const int MN = 2e5 + 10, ME=4*MN;
// maximum total value if we remove [left][right]; lazy increase; left & right value; left & right sign (nex - cur)
struct node{int tot[2][2], lInc, lef, rig, lSig, rSig;};
node seg[ME];
void push(int v){
if(2 * v + 1 < ME){
seg[2*v].lef += seg[v].lInc;
seg[2*v].rig += seg[v].lInc;
seg[2*v+1].lef += seg[v].lInc;
seg[2*v+1].rig += seg[v].lInc;
seg[v].lInc = 0;
}
}
void upd(int v, int nl, int nr, int ul, int ur, int by){
if(nl > ur || nr < ul) return;
else if(nl == ul && nr == ur){
seg[v].lInc += by;
seg[v].lef += by;
seg[v].rig += by;
} else {
push(v);
int mid = (nl + nr) / 2;
upd(2*v, nl, mid, ul, min(mid, ur), by);
upd(2*v+1, mid+1, nr, max(mid+1, ul), ur, by);
seg[v].lef = seg[2*v].lef;
seg[v].rig = seg[2*v+1].rig;
assert(seg[v].lInc == 0);
forR(lr, 2) forR(rr, 2){
int& edit = seg[v].tot[lr][rr];
edit = seg[2*v].tot[lr][0] + seg[2*v+1].tot[0][rr];
if(nr - mid - rr > 0 && mid - nl + 1 - lr > 0){
int delta = seg[2*v+1].lef - seg[2*v].rig;
int dSign = sign(delta);
int lefAdd = seg[2*v].rSig == dSign ? seg[2*v].tot[lr][0] : seg[2*v].tot[lr][1];
int rigAdd = seg[2*v+1].lSig == dSign ? seg[2*v+1].tot[0][rr] : seg[2*v+1].tot[1][rr];
edit = max(edit, lefAdd + abs(delta) + rigAdd);
}
}
seg[v].lSig = mid > nl ? seg[2*v].lSig : sign(seg[2*v+1].lef - seg[2*v].rig);
seg[v].rSig = mid + 1 < nr ? seg[2*v+1].rSig : sign(seg[2*v+1].lef - seg[2*v].rig);
}
}
signed main() {
int n, q; cin >> n >> q;
REP(i, 1, n + 1) {
int v; cin >> v;
upd(1, 1, n, i, i, v);
}
forR(g, q){
int l, r, x; cin >> l >> r >> x;
upd(1, 1, n, l, r, x);
cout << seg[1].tot[0][0] << '\n';
}
}
| # |
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 |
- |
