#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SegTree {
int n;
vector<int> st, add;
void push(int v, int vl, int vr) {
st[v] += add[v] * (vr - vl + 1);
if (vl != vr) {
add[v * 2] += add[v];
add[v * 2 + 1] += add[v];
}
add[v] = 0;
}
void update(int l, int r, int x, int v, int vl, int vr) {
push(v, vl, vr);
if (r < vl || vr < l) return;
if (l <= vl && vr <= r) {
add[v] += x;
push(v, vl, vr);
return;
}
int vm = (vl + vr) / 2;
update(l, r, x, v * 2, vl, vm);
update(l, r, x, v * 2 + 1, vm + 1, vr);
st[v] = st[v * 2] + st[v * 2 + 1];
}
SegTree(int n, vector<int> &a) {
this->n = n;
st.resize(4 * n);
add.resize(4 * n);
for (int i = 0; i < n; i++) {
update(i, i, a[i], 1, 0, n - 1);
}
}
int get(int l, int r, int v, int vl, int vr) {
push(v, vl, vr);
if (r < vl || vr < l) return 0;
if (l <= vl && vr <= r) return st[v];
int vm = (vl + vr) / 2;
return get(l, r, v * 2, vl, vm) + get(l, r, v * 2 + 1, vm + 1, vr);
}
int get(int pos) {
return get(pos, pos, 1, 0, n - 1);
}
};
int f(int x, int y, int s, int t) {
return (x < y ? s * (x - y) : t * (x - y));
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q, s, t;
cin >> n >> q >> s >> t;
n++;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
SegTree st(n, a);
int ans = 0;
for (int i = 0; i < n - 1; i++) {
ans += f(a[i], a[i + 1], s, t);
}
while (q--) {
int l, r, x;
cin >> l >> r >> x;
ans -= f(st.get(l - 1), st.get(l), s, t);
if (r < n - 1) ans -= f(st.get(r), st.get(r + 1), s, t);
st.update(l, r, x, 1, 0, n - 1);
ans += f(st.get(l - 1), st.get(l), s, t);
if (r < n - 1) ans += f(st.get(r), st.get(r + 1), s, t);
cout << ans << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
600 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
3 ms |
604 KB |
Output is correct |
4 |
Correct |
3 ms |
648 KB |
Output is correct |
5 |
Correct |
4 ms |
604 KB |
Output is correct |
6 |
Correct |
3 ms |
604 KB |
Output is correct |
7 |
Correct |
3 ms |
604 KB |
Output is correct |
8 |
Correct |
3 ms |
668 KB |
Output is correct |
9 |
Correct |
3 ms |
604 KB |
Output is correct |
10 |
Correct |
4 ms |
604 KB |
Output is correct |
11 |
Correct |
4 ms |
600 KB |
Output is correct |
12 |
Correct |
3 ms |
604 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
2 ms |
640 KB |
Output is correct |
15 |
Correct |
3 ms |
600 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
660 KB |
Output is correct |
18 |
Correct |
3 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
588 ms |
21332 KB |
Output is correct |
2 |
Correct |
559 ms |
21856 KB |
Output is correct |
3 |
Correct |
494 ms |
22356 KB |
Output is correct |
4 |
Correct |
475 ms |
21864 KB |
Output is correct |
5 |
Correct |
475 ms |
23124 KB |
Output is correct |
6 |
Correct |
516 ms |
22100 KB |
Output is correct |
7 |
Correct |
465 ms |
22092 KB |
Output is correct |
8 |
Correct |
398 ms |
23112 KB |
Output is correct |
9 |
Correct |
408 ms |
23120 KB |
Output is correct |
10 |
Correct |
378 ms |
21840 KB |
Output is correct |
11 |
Correct |
441 ms |
21840 KB |
Output is correct |
12 |
Correct |
481 ms |
22608 KB |
Output is correct |
13 |
Correct |
584 ms |
22864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
600 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
3 ms |
604 KB |
Output is correct |
4 |
Correct |
3 ms |
648 KB |
Output is correct |
5 |
Correct |
4 ms |
604 KB |
Output is correct |
6 |
Correct |
3 ms |
604 KB |
Output is correct |
7 |
Correct |
3 ms |
604 KB |
Output is correct |
8 |
Correct |
3 ms |
668 KB |
Output is correct |
9 |
Correct |
3 ms |
604 KB |
Output is correct |
10 |
Correct |
4 ms |
604 KB |
Output is correct |
11 |
Correct |
4 ms |
600 KB |
Output is correct |
12 |
Correct |
3 ms |
604 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
2 ms |
640 KB |
Output is correct |
15 |
Correct |
3 ms |
600 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
660 KB |
Output is correct |
18 |
Correct |
3 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
588 ms |
21332 KB |
Output is correct |
23 |
Correct |
559 ms |
21856 KB |
Output is correct |
24 |
Correct |
494 ms |
22356 KB |
Output is correct |
25 |
Correct |
475 ms |
21864 KB |
Output is correct |
26 |
Correct |
475 ms |
23124 KB |
Output is correct |
27 |
Correct |
516 ms |
22100 KB |
Output is correct |
28 |
Correct |
465 ms |
22092 KB |
Output is correct |
29 |
Correct |
398 ms |
23112 KB |
Output is correct |
30 |
Correct |
408 ms |
23120 KB |
Output is correct |
31 |
Correct |
378 ms |
21840 KB |
Output is correct |
32 |
Correct |
441 ms |
21840 KB |
Output is correct |
33 |
Correct |
481 ms |
22608 KB |
Output is correct |
34 |
Correct |
584 ms |
22864 KB |
Output is correct |
35 |
Correct |
506 ms |
21392 KB |
Output is correct |
36 |
Correct |
477 ms |
22864 KB |
Output is correct |
37 |
Correct |
537 ms |
23636 KB |
Output is correct |
38 |
Correct |
474 ms |
23376 KB |
Output is correct |
39 |
Correct |
468 ms |
23360 KB |
Output is correct |
40 |
Correct |
475 ms |
23380 KB |
Output is correct |
41 |
Correct |
507 ms |
23384 KB |
Output is correct |
42 |
Correct |
482 ms |
23308 KB |
Output is correct |
43 |
Correct |
463 ms |
22608 KB |
Output is correct |
44 |
Correct |
485 ms |
23120 KB |
Output is correct |
45 |
Correct |
466 ms |
22964 KB |
Output is correct |
46 |
Correct |
469 ms |
24148 KB |
Output is correct |
47 |
Correct |
511 ms |
22608 KB |
Output is correct |
48 |
Correct |
353 ms |
22672 KB |
Output is correct |
49 |
Correct |
492 ms |
21588 KB |
Output is correct |
50 |
Correct |
401 ms |
22460 KB |
Output is correct |
51 |
Correct |
510 ms |
22964 KB |
Output is correct |
52 |
Correct |
681 ms |
22716 KB |
Output is correct |