#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, x, y) for (int i = x; i < y; i++)
const ll mx1 = 2e5+5, mx2 = (1<<18), inf = LLONG_MAX/2;
ll n, q, sz, diff[mx1], mid[mx2], seg[mx2*2][2][2];
void upd(ll i, ll val){
i += sz; seg[i][1][0] = seg[i][0][1] = -inf; seg[i][1][1] = abs(val);
auto sgn = [](ll val){ return (val < 0) ? -1 : 1; };
for (i /= 2; i > 0; i /= 2){
FOR(l, 0, 2) FOR(r, 0, 2){ ll& curr = seg[i][l][r]; curr = -inf;
curr = max(curr, seg[i*2][l][0]+seg[i*2+1][0][r]);
curr = max(curr, seg[i*2][l][1]+seg[i*2+1][0][r]);
curr = max(curr, seg[i*2][l][0]+seg[i*2+1][1][r]);
if (sgn(diff[mid[i]])*sgn(diff[mid[i]+1]) != -1)
curr = max(curr, seg[i*2][l][1]+seg[i*2+1][1][r]);
}
}
}
int main(){
cin >> n >> q; sz = pow(2, ceil(log2(n-1)));
FOR(i, 1, sz){
int l = i, r = i;
while (r < sz) l = l*2, r = r*2+1;
mid[i] = (l+r)/2-sz; mid[i] = min(mid[i], mx1-1);
}ll prev; FOR(i, 0, n){
ll a; cin >> a;
if (i > 0) diff[i-1] = a-prev, upd(i-1, diff[i-1]);
prev = a;
}while (q--){
ll l, r, x; cin >> l >> r >> x; l--; r--;
if (l-1 >= 0) diff[l-1] += x, upd(l-1, diff[l-1]);
if (r < n-1) diff[r] -= x, upd(r, diff[r]);
cout<<max({seg[1][0][0], seg[1][1][0], seg[1][0][1], seg[1][1][1]})<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
14 ms |
704 KB |
Output is correct |
8 |
Correct |
18 ms |
688 KB |
Output is correct |
9 |
Correct |
14 ms |
704 KB |
Output is correct |
10 |
Correct |
16 ms |
672 KB |
Output is correct |
11 |
Correct |
15 ms |
588 KB |
Output is correct |
12 |
Correct |
19 ms |
708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
14 ms |
704 KB |
Output is correct |
8 |
Correct |
18 ms |
688 KB |
Output is correct |
9 |
Correct |
14 ms |
704 KB |
Output is correct |
10 |
Correct |
16 ms |
672 KB |
Output is correct |
11 |
Correct |
15 ms |
588 KB |
Output is correct |
12 |
Correct |
19 ms |
708 KB |
Output is correct |
13 |
Correct |
1411 ms |
25564 KB |
Output is correct |
14 |
Correct |
1343 ms |
25612 KB |
Output is correct |
15 |
Correct |
1363 ms |
25540 KB |
Output is correct |
16 |
Correct |
1293 ms |
25708 KB |
Output is correct |
17 |
Correct |
1314 ms |
25408 KB |
Output is correct |
18 |
Correct |
1247 ms |
26220 KB |
Output is correct |