#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()
const int mxn = 2e5 + 10;
ll a[mxn];
struct SegmentTree {
vector<ll> sgt, lz;
SegmentTree(int sz) {
sgt.resize(4 * sz);
lz.resize(4 * sz);
}
void build(int k, int l, int r) {
if (l == r) {
sgt[k] = a[l];
return;
}
int m = (l + r) / 2;
build(k * 2, l, m);
build(k * 2 + 1, m + 1, r);
}
void push(int k, int l, int r) {
if (lz[k]) {
sgt[k] += lz[k];
if (l != r) {
lz[k * 2] += lz[k];
lz[k * 2 + 1] += lz[k];
}
lz[k] = 0;
}
}
void update(int k, int l, int r, int i, int j, ll val) {
push(k, l, r);
if (l > j || r < i) return;
if (i <= l && r <= j) {
lz[k] += val;
push(k, l, r);
return;
}
int m = (l + r) / 2;
update(k * 2, l, m, i, j, val);
update(k * 2 + 1, m + 1, r, i, j, val);
}
ll get(int k, int l, int r, int i) {
push(k, l, r);
if (l == r) return sgt[k];
int m = (l + r) / 2;
if (m >= i) return get(k * 2, l, m, i);
return get(k * 2 + 1, m + 1, r, i);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q, s, t;
cin >> n >> q >> s >> t;
n++;
for (int i = 0; i < n; i++) cin >> a[i];
SegmentTree sgt(n);
sgt.build(1, 0, n - 1);
ll ans = 0;
for (int i = 1; i < n; i++) {
if (a[i - 1] < a[i]) ans += (a[i] - a[i - 1]) * s;
else ans += (a[i] - a[i - 1]) * t;
}
while (q--) {
int l, r, x;
cin >> l >> r >> x;
a[l - 1] = sgt.get(1, 0, n - 1, l - 1);
a[l] = sgt.get(1, 0, n - 1, l);
if (a[l - 1] < a[l]) ans -= (a[l] - a[l - 1]) * s;
else ans -= (a[l] - a[l - 1]) * t;
if (l < n - 1) {
a[l + 1] = sgt.get(1, 0, n - 1, l + 1);
if (a[l] < a[l + 1]) ans -= (a[l + 1] - a[l]) * s;
else ans -= (a[l + 1] - a[l]) * t;
}
if (l != r) {
if (l + 1 < r) {
a[r - 1] = sgt.get(1, 0, n - 1, r - 1);
a[r] = sgt.get(1, 0, n - 1, r);
if (a[r - 1] < a[r]) ans -= (a[r] - a[r - 1]) * s;
else ans -= (a[r] - a[r - 1]) * t;
}
if (r < n - 1) {
a[r + 1] = sgt.get(1, 0, n - 1, r + 1);
if (a[r] < a[r + 1]) ans -= (a[r + 1] - a[r]) * s;
else ans -= (a[r + 1] - a[r]) * t;
}
}
sgt.update(1, 0, n - 1, l, r, x);
a[l - 1] = sgt.get(1, 0, n - 1, l - 1);
a[l] = sgt.get(1, 0, n - 1, l);
if (a[l - 1] < a[l]) ans += (a[l] - a[l - 1]) * s;
else ans += (a[l] - a[l - 1]) * t;
if (l < n - 1) {
a[l + 1] = sgt.get(1, 0, n - 1, l + 1);
if (a[l] < a[l + 1]) ans += (a[l + 1] - a[l]) * s;
else ans += (a[l + 1] - a[l]) * t;
}
if (l != r) {
if (l + 1 < r) {
a[r - 1] = sgt.get(1, 0, n - 1, r - 1);
a[r] = sgt.get(1, 0, n - 1, r);
if (a[r - 1] < a[r]) ans += (a[r] - a[r - 1]) * s;
else ans += (a[r] - a[r - 1]) * t;
}
if (r < n - 1) {
a[r + 1] = sgt.get(1, 0, n - 1, r + 1);
if (a[r] < a[r + 1]) ans += (a[r + 1] - a[r]) * s;
else ans += (a[r + 1] - a[r]) * t;
}
}
cout << -ans << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
3 ms |
680 KB |
Output is correct |
3 |
Correct |
4 ms |
600 KB |
Output is correct |
4 |
Correct |
4 ms |
656 KB |
Output is correct |
5 |
Correct |
3 ms |
604 KB |
Output is correct |
6 |
Correct |
3 ms |
676 KB |
Output is correct |
7 |
Correct |
4 ms |
600 KB |
Output is correct |
8 |
Correct |
4 ms |
604 KB |
Output is correct |
9 |
Correct |
3 ms |
672 KB |
Output is correct |
10 |
Correct |
3 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
604 KB |
Output is correct |
12 |
Correct |
3 ms |
604 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
3 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
456 ms |
21192 KB |
Output is correct |
2 |
Correct |
445 ms |
21988 KB |
Output is correct |
3 |
Correct |
440 ms |
22352 KB |
Output is correct |
4 |
Correct |
428 ms |
22284 KB |
Output is correct |
5 |
Correct |
421 ms |
23104 KB |
Output is correct |
6 |
Correct |
236 ms |
22032 KB |
Output is correct |
7 |
Correct |
231 ms |
22104 KB |
Output is correct |
8 |
Correct |
396 ms |
22920 KB |
Output is correct |
9 |
Correct |
393 ms |
23376 KB |
Output is correct |
10 |
Correct |
391 ms |
21828 KB |
Output is correct |
11 |
Correct |
185 ms |
21984 KB |
Output is correct |
12 |
Correct |
228 ms |
22608 KB |
Output is correct |
13 |
Correct |
235 ms |
22980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
3 ms |
680 KB |
Output is correct |
3 |
Correct |
4 ms |
600 KB |
Output is correct |
4 |
Correct |
4 ms |
656 KB |
Output is correct |
5 |
Correct |
3 ms |
604 KB |
Output is correct |
6 |
Correct |
3 ms |
676 KB |
Output is correct |
7 |
Correct |
4 ms |
600 KB |
Output is correct |
8 |
Correct |
4 ms |
604 KB |
Output is correct |
9 |
Correct |
3 ms |
672 KB |
Output is correct |
10 |
Correct |
3 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
604 KB |
Output is correct |
12 |
Correct |
3 ms |
604 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
3 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
464 KB |
Output is correct |
22 |
Correct |
456 ms |
21192 KB |
Output is correct |
23 |
Correct |
445 ms |
21988 KB |
Output is correct |
24 |
Correct |
440 ms |
22352 KB |
Output is correct |
25 |
Correct |
428 ms |
22284 KB |
Output is correct |
26 |
Correct |
421 ms |
23104 KB |
Output is correct |
27 |
Correct |
236 ms |
22032 KB |
Output is correct |
28 |
Correct |
231 ms |
22104 KB |
Output is correct |
29 |
Correct |
396 ms |
22920 KB |
Output is correct |
30 |
Correct |
393 ms |
23376 KB |
Output is correct |
31 |
Correct |
391 ms |
21828 KB |
Output is correct |
32 |
Correct |
185 ms |
21984 KB |
Output is correct |
33 |
Correct |
228 ms |
22608 KB |
Output is correct |
34 |
Correct |
235 ms |
22980 KB |
Output is correct |
35 |
Correct |
419 ms |
21412 KB |
Output is correct |
36 |
Correct |
445 ms |
22968 KB |
Output is correct |
37 |
Correct |
421 ms |
23620 KB |
Output is correct |
38 |
Correct |
472 ms |
23380 KB |
Output is correct |
39 |
Correct |
450 ms |
23332 KB |
Output is correct |
40 |
Correct |
430 ms |
23384 KB |
Output is correct |
41 |
Correct |
451 ms |
23144 KB |
Output is correct |
42 |
Correct |
443 ms |
23452 KB |
Output is correct |
43 |
Correct |
447 ms |
22784 KB |
Output is correct |
44 |
Correct |
429 ms |
23020 KB |
Output is correct |
45 |
Correct |
476 ms |
22960 KB |
Output is correct |
46 |
Correct |
427 ms |
24068 KB |
Output is correct |
47 |
Correct |
273 ms |
22664 KB |
Output is correct |
48 |
Correct |
135 ms |
22636 KB |
Output is correct |
49 |
Correct |
435 ms |
21708 KB |
Output is correct |
50 |
Correct |
193 ms |
22464 KB |
Output is correct |
51 |
Correct |
254 ms |
22776 KB |
Output is correct |
52 |
Correct |
217 ms |
22608 KB |
Output is correct |