#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N = 2e5;
const int MOD = 998244353;
struct Node {
int ans, prefMax, prefMin, sufMax, sufMin, lazy;
};
Node segm[4*MAX_N];
void push(int pos, int l, int r) {
segm[pos].prefMax += segm[pos].lazy;
segm[pos].sufMax += segm[pos].lazy;
segm[pos].prefMin -= segm[pos].lazy;
segm[pos].sufMin -= segm[pos].lazy;
if(l==r) {
segm[pos].lazy = 0;
return;
}
segm[2*pos+1].lazy += segm[pos].lazy;
segm[2*pos+2].lazy += segm[pos].lazy;
segm[pos].lazy = 0;
}
void calc(int pos, int l, int r) {
if(l==r) {
segm[pos].ans = 0;
return;
}
int m = (l+r)/2;
push(2*pos+1, l, m);
push(2*pos+2, m+1, r);
calc(2*pos+1, l, m);
calc(2*pos+2, m+1, r);
segm[pos].ans = segm[2*pos+1].ans + segm[2*pos+2].ans;
segm[pos].ans = max(segm[pos].ans, segm[2*pos+1].sufMin + segm[2*pos+2].prefMax);
segm[pos].ans = max(segm[pos].ans, segm[2*pos+1].sufMax + segm[2*pos+2].prefMin);
segm[pos].prefMin = max(segm[2*pos+1].prefMin + segm[2*pos+2].ans, segm[2*pos+2].prefMin);
segm[pos].prefMax = max(segm[2*pos+1].prefMax + segm[2*pos+2].ans, segm[2*pos+2].prefMax);
segm[pos].sufMin = max(segm[2*pos+2].sufMin + segm[2*pos+1].ans, segm[2*pos+1].sufMin);
segm[pos].sufMax = max(segm[2*pos+2].sufMax + segm[2*pos+1].ans, segm[2*pos+1].sufMax);
}
void update(int pos, int l, int r, int L, int R, int val) {
if(l >= L && r <= R) segm[pos].lazy += val;
push(pos, l, r);
if(l < L or r > R) {
int m = (l+r)/2;
if(m >= L) update(2*pos+1, l, m, L, R, val);
if(m+1 <= R) update(2*pos+2, m+1, r, L, R, val);
}
calc(pos, l, r);
}
void solve() {
for(int i=0; i<4*MAX_N; ++i) segm[i].ans = segm[i].lazy = segm[i].prefMax = segm[i].prefMin = segm[i].sufMax = segm[i].sufMin = 0;
int n, q;
cin >> n >> q;
for(int i=0; i<n; ++i) {
int x;
cin >> x;
update(1, 0, n-1, i, i, x);
}
while(q--) {
int l, r, x;
cin >> l >> r >> x;
--l, --r;
update(1, 0, n-1, l, r, x);
cout << segm[1].ans << endl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while(t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
