#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> a;
vector<ll> st, lz;
ll bld(int nd, int l, int r) {
if (l == r) {
return st[nd] = a[l];
}
int ch = nd<<1, md = (l + r)>>1;
return st[nd] = bld(ch, l, md) + bld(ch + 1, md + 1, r);
}
void LZ(int nd, int l, int r) {
st[nd] += (r - l + 1) * lz[nd];
if (l != r) {
int ch = nd<<1;
lz[ch] += lz[nd];
lz[ch + 1] += lz[nd];
}
lz[nd] = 0;
}
void upd(int nd, int l, int r, int x, int y, int val) {
LZ(nd, l, r);
if (r < x || y < l) return;
if (x <= l && r <= y) {
lz[nd] += val;
}
else {
int ch = nd<<1, md = (l + r)>>1;
upd(ch, l, md, x, y, val);
upd(ch + 1, md + 1, r, x, y, val);
}
}
ll fnd(int nd, int l, int r, int x) {
LZ(nd, l, r);
if (l > x || x > r) return 0;
if (l == r) return st[nd];
int ch = nd<<1, md = (l + r)>>1;
return fnd(ch, l, md, x) + fnd(ch + 1, md + 1, r, x);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q, s, t;
cin >> n >> q >> s >> t;
a.assign(n + 1, 0);
st.assign((n<<2) + 5, 0);
lz.assign((n<<2) + 5, 0);
ll ans = 0;
for (int i = 0; i <= n; i++) {
cin >> a[i];
if (i) ans += 1LL * (a[i - 1] < a[i] ? s : t) * (a[i - 1] - a[i]);
}
bld(1, 0, n);
while (q--) {
int l, r, x;
cin >> l >> r >> x;
if (l) {
ll y = fnd(1, 0, n, l - 1), z = fnd(1, 0, n, l);
ans -= 1LL * (y < z ? s : t) * (y - z);
}
if (r != n) {
ll y = fnd(1, 0, n, r), z = fnd(1, 0, n, r + 1);
ans -= 1LL * (y < z ? s : t) * (y - z);
}
upd(1, 0, n, l, r, x);
if (l) {
ll y = fnd(1, 0, n, l - 1), z = fnd(1, 0, n, l);
ans += 1LL * (y < z ? s : t) * (y - z);
}
if (r != n) {
ll y = fnd(1, 0, n, r), z = fnd(1, 0, n, r + 1);
ans += 1LL * (y < z ? s : t) * (y - z);
}
cout << ans << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
600 KB |
Output is correct |
2 |
Correct |
3 ms |
600 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
604 KB |
Output is correct |
5 |
Correct |
4 ms |
600 KB |
Output is correct |
6 |
Correct |
4 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
4 ms |
604 KB |
Output is correct |
9 |
Correct |
4 ms |
600 KB |
Output is correct |
10 |
Correct |
3 ms |
600 KB |
Output is correct |
11 |
Correct |
4 ms |
604 KB |
Output is correct |
12 |
Correct |
3 ms |
600 KB |
Output is correct |
13 |
Correct |
2 ms |
600 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
4 ms |
600 KB |
Output is correct |
16 |
Correct |
3 ms |
600 KB |
Output is correct |
17 |
Correct |
2 ms |
600 KB |
Output is correct |
18 |
Correct |
3 ms |
856 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
452 ms |
15184 KB |
Output is correct |
2 |
Correct |
462 ms |
15820 KB |
Output is correct |
3 |
Correct |
469 ms |
16208 KB |
Output is correct |
4 |
Correct |
473 ms |
15508 KB |
Output is correct |
5 |
Correct |
471 ms |
16148 KB |
Output is correct |
6 |
Correct |
366 ms |
16976 KB |
Output is correct |
7 |
Correct |
328 ms |
16564 KB |
Output is correct |
8 |
Correct |
383 ms |
16436 KB |
Output is correct |
9 |
Correct |
366 ms |
17004 KB |
Output is correct |
10 |
Correct |
389 ms |
15740 KB |
Output is correct |
11 |
Correct |
364 ms |
16748 KB |
Output is correct |
12 |
Correct |
323 ms |
17100 KB |
Output is correct |
13 |
Correct |
333 ms |
22120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
600 KB |
Output is correct |
2 |
Correct |
3 ms |
600 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
604 KB |
Output is correct |
5 |
Correct |
4 ms |
600 KB |
Output is correct |
6 |
Correct |
4 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
4 ms |
604 KB |
Output is correct |
9 |
Correct |
4 ms |
600 KB |
Output is correct |
10 |
Correct |
3 ms |
600 KB |
Output is correct |
11 |
Correct |
4 ms |
604 KB |
Output is correct |
12 |
Correct |
3 ms |
600 KB |
Output is correct |
13 |
Correct |
2 ms |
600 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
4 ms |
600 KB |
Output is correct |
16 |
Correct |
3 ms |
600 KB |
Output is correct |
17 |
Correct |
2 ms |
600 KB |
Output is correct |
18 |
Correct |
3 ms |
856 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
452 ms |
15184 KB |
Output is correct |
23 |
Correct |
462 ms |
15820 KB |
Output is correct |
24 |
Correct |
469 ms |
16208 KB |
Output is correct |
25 |
Correct |
473 ms |
15508 KB |
Output is correct |
26 |
Correct |
471 ms |
16148 KB |
Output is correct |
27 |
Correct |
366 ms |
16976 KB |
Output is correct |
28 |
Correct |
328 ms |
16564 KB |
Output is correct |
29 |
Correct |
383 ms |
16436 KB |
Output is correct |
30 |
Correct |
366 ms |
17004 KB |
Output is correct |
31 |
Correct |
389 ms |
15740 KB |
Output is correct |
32 |
Correct |
364 ms |
16748 KB |
Output is correct |
33 |
Correct |
323 ms |
17100 KB |
Output is correct |
34 |
Correct |
333 ms |
22120 KB |
Output is correct |
35 |
Correct |
441 ms |
18332 KB |
Output is correct |
36 |
Correct |
487 ms |
21376 KB |
Output is correct |
37 |
Correct |
481 ms |
22864 KB |
Output is correct |
38 |
Correct |
500 ms |
22592 KB |
Output is correct |
39 |
Correct |
488 ms |
22740 KB |
Output is correct |
40 |
Correct |
500 ms |
22848 KB |
Output is correct |
41 |
Correct |
467 ms |
22508 KB |
Output is correct |
42 |
Correct |
462 ms |
22608 KB |
Output is correct |
43 |
Correct |
503 ms |
21968 KB |
Output is correct |
44 |
Correct |
459 ms |
22276 KB |
Output is correct |
45 |
Correct |
463 ms |
22348 KB |
Output is correct |
46 |
Correct |
464 ms |
23488 KB |
Output is correct |
47 |
Correct |
387 ms |
21872 KB |
Output is correct |
48 |
Correct |
327 ms |
21856 KB |
Output is correct |
49 |
Correct |
479 ms |
20996 KB |
Output is correct |
50 |
Correct |
374 ms |
21808 KB |
Output is correct |
51 |
Correct |
331 ms |
21992 KB |
Output is correct |
52 |
Correct |
481 ms |
21840 KB |
Output is correct |