#include <bits/stdc++.h>
using namespace std;
long long n, q, s, t, a[200010], node[1000010], l, r, val, tmpl, tmpr, tnpl, tnpr, ans, tmp, tnp;
void update(int id, int x, int y) {
if ((r < x) || (y < l)) return;
if ((l <= x) && (y <= r)) {
node[id] += val;
return;
}
int mid = (x+y)/2;
update(id*2,x,mid);
update(id*2+1,mid+1,y);
}
long long find(int id, int x, int y, int pos) {
if (x == y) return a[x]+node[id];
int mid = (x+y)/2;
node[id*2] += node[id];
node[id*2+1] += node[id];
node[id] = 0;
if (pos <= mid) return find(id*2,x,mid,pos);
else return find(id*2+1,mid+1,y,pos);
}
int main() {
cin >> n >> q >> s >> t;
for (int i = 0; i <= n; i++) {
cin >> a[i];
if (i > 0) {
if (a[i] > a[i-1]) ans += s*(a[i-1]-a[i]);
else ans += t*(a[i-1]-a[i]);
}
}
while (q--) {
cin >> l >> r >> val;
if (r == n) tmpr = 0;
else {
tmp = find(1,0,n,r);
tnp = find(1,0,n,r+1);
if (tmp > tnp) tmpr = (tmp-tnp)*t;
else tmpr = (tmp-tnp)*s;
}
tmp = find(1,0,n,l);
tnp = find(1,0,n,l-1);
if (tmp > tnp) tmpl = (tnp-tmp)*s;
else tmpl = (tnp-tmp)*t;
update(1,0,n);
if (r == n) tnpr = 0;
else {
tmp = find(1,0,n,r);
tnp = find(1,0,n,r+1);
if (tmp > tnp) tnpr = (tmp-tnp)*t;
else tnpr = (tmp-tnp)*s;
}
tmp = find(1,0,n,l);
tnp = find(1,0,n,l-1);
if (tmp > tnp) tnpl = (tnp-tmp)*s;
else tnpl = (tnp-tmp)*t;
ans += (tnpl-tmpl)+(tnpr-tmpr);
cout << ans << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2392 KB |
Output is correct |
2 |
Correct |
6 ms |
2396 KB |
Output is correct |
3 |
Correct |
6 ms |
2396 KB |
Output is correct |
4 |
Correct |
6 ms |
2396 KB |
Output is correct |
5 |
Correct |
6 ms |
2396 KB |
Output is correct |
6 |
Correct |
6 ms |
2536 KB |
Output is correct |
7 |
Correct |
6 ms |
2392 KB |
Output is correct |
8 |
Correct |
6 ms |
2396 KB |
Output is correct |
9 |
Correct |
6 ms |
2396 KB |
Output is correct |
10 |
Correct |
6 ms |
2396 KB |
Output is correct |
11 |
Correct |
6 ms |
2396 KB |
Output is correct |
12 |
Correct |
6 ms |
2396 KB |
Output is correct |
13 |
Correct |
5 ms |
2524 KB |
Output is correct |
14 |
Correct |
5 ms |
2396 KB |
Output is correct |
15 |
Correct |
6 ms |
2396 KB |
Output is correct |
16 |
Correct |
5 ms |
2508 KB |
Output is correct |
17 |
Correct |
5 ms |
2516 KB |
Output is correct |
18 |
Correct |
5 ms |
2396 KB |
Output is correct |
19 |
Correct |
1 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
605 ms |
13676 KB |
Output is correct |
2 |
Correct |
610 ms |
15184 KB |
Output is correct |
3 |
Correct |
644 ms |
15700 KB |
Output is correct |
4 |
Correct |
631 ms |
15224 KB |
Output is correct |
5 |
Correct |
633 ms |
16356 KB |
Output is correct |
6 |
Correct |
471 ms |
13144 KB |
Output is correct |
7 |
Correct |
465 ms |
13132 KB |
Output is correct |
8 |
Correct |
668 ms |
15988 KB |
Output is correct |
9 |
Correct |
583 ms |
16408 KB |
Output is correct |
10 |
Correct |
592 ms |
15272 KB |
Output is correct |
11 |
Correct |
471 ms |
13008 KB |
Output is correct |
12 |
Correct |
471 ms |
13652 KB |
Output is correct |
13 |
Correct |
460 ms |
13872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2392 KB |
Output is correct |
2 |
Correct |
6 ms |
2396 KB |
Output is correct |
3 |
Correct |
6 ms |
2396 KB |
Output is correct |
4 |
Correct |
6 ms |
2396 KB |
Output is correct |
5 |
Correct |
6 ms |
2396 KB |
Output is correct |
6 |
Correct |
6 ms |
2536 KB |
Output is correct |
7 |
Correct |
6 ms |
2392 KB |
Output is correct |
8 |
Correct |
6 ms |
2396 KB |
Output is correct |
9 |
Correct |
6 ms |
2396 KB |
Output is correct |
10 |
Correct |
6 ms |
2396 KB |
Output is correct |
11 |
Correct |
6 ms |
2396 KB |
Output is correct |
12 |
Correct |
6 ms |
2396 KB |
Output is correct |
13 |
Correct |
5 ms |
2524 KB |
Output is correct |
14 |
Correct |
5 ms |
2396 KB |
Output is correct |
15 |
Correct |
6 ms |
2396 KB |
Output is correct |
16 |
Correct |
5 ms |
2508 KB |
Output is correct |
17 |
Correct |
5 ms |
2516 KB |
Output is correct |
18 |
Correct |
5 ms |
2396 KB |
Output is correct |
19 |
Correct |
1 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
22 |
Correct |
605 ms |
13676 KB |
Output is correct |
23 |
Correct |
610 ms |
15184 KB |
Output is correct |
24 |
Correct |
644 ms |
15700 KB |
Output is correct |
25 |
Correct |
631 ms |
15224 KB |
Output is correct |
26 |
Correct |
633 ms |
16356 KB |
Output is correct |
27 |
Correct |
471 ms |
13144 KB |
Output is correct |
28 |
Correct |
465 ms |
13132 KB |
Output is correct |
29 |
Correct |
668 ms |
15988 KB |
Output is correct |
30 |
Correct |
583 ms |
16408 KB |
Output is correct |
31 |
Correct |
592 ms |
15272 KB |
Output is correct |
32 |
Correct |
471 ms |
13008 KB |
Output is correct |
33 |
Correct |
471 ms |
13652 KB |
Output is correct |
34 |
Correct |
460 ms |
13872 KB |
Output is correct |
35 |
Correct |
647 ms |
14716 KB |
Output is correct |
36 |
Correct |
628 ms |
16364 KB |
Output is correct |
37 |
Correct |
650 ms |
16964 KB |
Output is correct |
38 |
Correct |
648 ms |
16600 KB |
Output is correct |
39 |
Correct |
616 ms |
16556 KB |
Output is correct |
40 |
Correct |
697 ms |
16804 KB |
Output is correct |
41 |
Correct |
632 ms |
16532 KB |
Output is correct |
42 |
Correct |
646 ms |
16884 KB |
Output is correct |
43 |
Correct |
624 ms |
15840 KB |
Output is correct |
44 |
Correct |
652 ms |
16308 KB |
Output is correct |
45 |
Correct |
622 ms |
16668 KB |
Output is correct |
46 |
Correct |
632 ms |
17532 KB |
Output is correct |
47 |
Correct |
491 ms |
13796 KB |
Output is correct |
48 |
Correct |
527 ms |
13652 KB |
Output is correct |
49 |
Correct |
600 ms |
14932 KB |
Output is correct |
50 |
Correct |
474 ms |
13396 KB |
Output is correct |
51 |
Correct |
477 ms |
14176 KB |
Output is correct |
52 |
Correct |
548 ms |
16220 KB |
Output is correct |