#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 200005
struct node {
ll left, right;
ll l0r0, l0r1, l1r0, l1r1;
};
node merge(node a, node b) {
node temp;
temp.left = a.left;
temp.right = b.right;
if (a.right * b.left < 0) {
temp.l1r1 = max(abs(a.l1r0) + abs(b.l1r1), abs(a.l1r1) + abs(b.l0r1));
temp.l1r0 = max(abs(a.l1r0) + abs(b.l1r0), abs(a.l1r1) + abs(b.l0r0));
temp.l0r1 = max(abs(a.l0r0) + abs(b.l1r1), abs(a.l0r1) + abs(b.l0r1));
temp.l0r0 = max(abs(a.l0r0) + abs(b.l1r0), abs(a.l0r1) + abs(b.l0r0));
} else {
temp.l1r1 = abs(a.l1r1) + abs(b.l1r1);
temp.l1r0 = abs(a.l1r1) + abs(b.l1r0);
temp.l0r1 = abs(a.l0r1) + abs(b.l1r1);
temp.l0r0 = abs(a.l0r1) + abs(b.l1r0);
}
return temp;
}
vector<ll> arr, diff;
node sg[4*MAXN];
void init(int k, int a, int b) {
if (a == b) {
sg[k].left = sg[k].right = sg[k].l1r1 = diff[a];
sg[k].l0r0 = sg[k].l0r1 = sg[k].l1r0 = 0;
return ;
}
init(2*k, a, (a+b)/2);
init(2*k+1, (a+b)/2+1, b);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
void point_update(int k, int a, int b, int plc, ll val) {
if (a > plc || b < plc)
return ;
if (a == b) {
sg[k].left = sg[k].right += val;
sg[k].l1r1 = abs(sg[k].right);
sg[k].l0r0 = sg[k].l0r1 = sg[k].l1r0 = 0;
return ;
}
point_update(2*k, a, (a+b)/2, plc, val);
point_update(2*k+1, (a+b)/2+1, b, plc, val);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
int main() {
fast
ll n, q;
cin >> n >> q;
arr = vector<ll>(n+1);
diff = vector<ll>(n+1);
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 2; i <= n; i++)
diff[i-1] = arr[i] - arr[i-1];
init(1, 1, n-1);
while (q--) {
ll l, r, val;
cin >> l >> r >> val;
if (l != 1)
point_update(1, 1, n-1, l-1, val);
if (r != n)
point_update(1, 1, n-1, r, -val);
cout << sg[1].l1r1 << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
4 ms |
852 KB |
Output is correct |
8 |
Correct |
4 ms |
856 KB |
Output is correct |
9 |
Correct |
4 ms |
852 KB |
Output is correct |
10 |
Correct |
4 ms |
852 KB |
Output is correct |
11 |
Correct |
4 ms |
852 KB |
Output is correct |
12 |
Correct |
5 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
4 ms |
852 KB |
Output is correct |
8 |
Correct |
4 ms |
856 KB |
Output is correct |
9 |
Correct |
4 ms |
852 KB |
Output is correct |
10 |
Correct |
4 ms |
852 KB |
Output is correct |
11 |
Correct |
4 ms |
852 KB |
Output is correct |
12 |
Correct |
5 ms |
852 KB |
Output is correct |
13 |
Correct |
375 ms |
37148 KB |
Output is correct |
14 |
Correct |
410 ms |
37216 KB |
Output is correct |
15 |
Correct |
417 ms |
37188 KB |
Output is correct |
16 |
Correct |
443 ms |
37032 KB |
Output is correct |
17 |
Correct |
377 ms |
37004 KB |
Output is correct |
18 |
Correct |
404 ms |
37736 KB |
Output is correct |