#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"
#define int long long
using namespace std;
const int sz = 2e5 + 10;
int st[sz * 8], lz[sz * 8], a[sz], b[sz];
void build(int le, int ri, int v) {
if (le == ri) {
st[v] = a[le];
return;
}
int mi = le + (ri - le) / 2;
build(le, mi, v * 2);
build(mi + 1, ri, v * 2 + 1);
}
void relax(int v) {
st[v] += lz[v];
lz[v * 2] += lz[v];
lz[v * 2 + 1] += lz[v];
lz[v] = 0;
}
void update(int le, int ri, int ql, int qr, int v, int k) {
if (le > qr || ri < ql) return;
if (ql <= le && ri <= qr) {
lz[v] += k;
relax(v);
return;
}
int mi = le + (ri - le) / 2;
update(le, mi, ql, qr, v * 2, k);
update(mi + 1, ri, ql, qr, v * 2 + 1, k);
}
int query(int le, int ri, int ql, int qr, int v) {
relax(v);
if (le > qr || ri < ql) return 0;
if (ql <= le && ri <= qr) {
a[le] = st[v];
return st[v];
}
int mi = le + (ri - le) / 2;
int lq = query(le, mi, ql, qr, v * 2);
int rq = query(mi + 1, ri, ql, qr, v * 2 + 1);
return lq + rq;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q, s, t;
cin >> n >> q >> s >> t;
int tm;
cin >> tm;
int r = 0;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
int d = a[i - 1] - a[i];
if (0 < d) {
b[i] = d * t;
} else {
b[i] = d * s;
}
r += b[i];
}
build(1, n, 1);
while (q --) {
int le, ri, x;
cin >> le >> ri >> x;
update(1, n, le, ri, 1, x);
query(1, n, le, le, 1);
query(1, n, ri, ri, 1);
query(1, n, le - 1, le - 1, 1);
if (ri + 1 <= n) {
query(1, n, ri + 1, ri + 1, 1);
}
// cout << a[le] << ' ' << a[ri] << '\n';
r -= b[le];
int d = a[le - 1] - a[le];
if (0 < d) {
b[le] = d * t;
} else {
b[le] = d * s;
}
if (ri + 1 <= n) {
d = a[ri] - a[ri + 1];
r -= b[ri + 1];
if (0 < d) {
b[ri + 1] = d * t;
} else {
b[ri + 1] = d * s;
}
r += b[ri + 1];
}
r += b[le];
cout << r << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4440 KB |
Output is correct |
2 |
Correct |
2 ms |
4700 KB |
Output is correct |
3 |
Correct |
3 ms |
4696 KB |
Output is correct |
4 |
Correct |
3 ms |
4952 KB |
Output is correct |
5 |
Correct |
2 ms |
4700 KB |
Output is correct |
6 |
Correct |
2 ms |
4700 KB |
Output is correct |
7 |
Correct |
2 ms |
4700 KB |
Output is correct |
8 |
Correct |
2 ms |
4700 KB |
Output is correct |
9 |
Correct |
2 ms |
4700 KB |
Output is correct |
10 |
Correct |
2 ms |
4700 KB |
Output is correct |
11 |
Correct |
2 ms |
4700 KB |
Output is correct |
12 |
Correct |
2 ms |
4640 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
2 ms |
4696 KB |
Output is correct |
15 |
Correct |
2 ms |
4700 KB |
Output is correct |
16 |
Correct |
2 ms |
4700 KB |
Output is correct |
17 |
Correct |
2 ms |
4440 KB |
Output is correct |
18 |
Correct |
2 ms |
4660 KB |
Output is correct |
19 |
Correct |
1 ms |
4440 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
0 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
254 ms |
20428 KB |
Output is correct |
2 |
Correct |
260 ms |
26448 KB |
Output is correct |
3 |
Correct |
249 ms |
26964 KB |
Output is correct |
4 |
Correct |
235 ms |
26452 KB |
Output is correct |
5 |
Correct |
247 ms |
27608 KB |
Output is correct |
6 |
Correct |
124 ms |
22608 KB |
Output is correct |
7 |
Correct |
117 ms |
22356 KB |
Output is correct |
8 |
Correct |
221 ms |
27476 KB |
Output is correct |
9 |
Correct |
221 ms |
27736 KB |
Output is correct |
10 |
Correct |
216 ms |
26516 KB |
Output is correct |
11 |
Correct |
148 ms |
20308 KB |
Output is correct |
12 |
Correct |
120 ms |
23124 KB |
Output is correct |
13 |
Correct |
179 ms |
21328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4440 KB |
Output is correct |
2 |
Correct |
2 ms |
4700 KB |
Output is correct |
3 |
Correct |
3 ms |
4696 KB |
Output is correct |
4 |
Correct |
3 ms |
4952 KB |
Output is correct |
5 |
Correct |
2 ms |
4700 KB |
Output is correct |
6 |
Correct |
2 ms |
4700 KB |
Output is correct |
7 |
Correct |
2 ms |
4700 KB |
Output is correct |
8 |
Correct |
2 ms |
4700 KB |
Output is correct |
9 |
Correct |
2 ms |
4700 KB |
Output is correct |
10 |
Correct |
2 ms |
4700 KB |
Output is correct |
11 |
Correct |
2 ms |
4700 KB |
Output is correct |
12 |
Correct |
2 ms |
4640 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
2 ms |
4696 KB |
Output is correct |
15 |
Correct |
2 ms |
4700 KB |
Output is correct |
16 |
Correct |
2 ms |
4700 KB |
Output is correct |
17 |
Correct |
2 ms |
4440 KB |
Output is correct |
18 |
Correct |
2 ms |
4660 KB |
Output is correct |
19 |
Correct |
1 ms |
4440 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
0 ms |
4444 KB |
Output is correct |
22 |
Correct |
254 ms |
20428 KB |
Output is correct |
23 |
Correct |
260 ms |
26448 KB |
Output is correct |
24 |
Correct |
249 ms |
26964 KB |
Output is correct |
25 |
Correct |
235 ms |
26452 KB |
Output is correct |
26 |
Correct |
247 ms |
27608 KB |
Output is correct |
27 |
Correct |
124 ms |
22608 KB |
Output is correct |
28 |
Correct |
117 ms |
22356 KB |
Output is correct |
29 |
Correct |
221 ms |
27476 KB |
Output is correct |
30 |
Correct |
221 ms |
27736 KB |
Output is correct |
31 |
Correct |
216 ms |
26516 KB |
Output is correct |
32 |
Correct |
148 ms |
20308 KB |
Output is correct |
33 |
Correct |
120 ms |
23124 KB |
Output is correct |
34 |
Correct |
179 ms |
21328 KB |
Output is correct |
35 |
Correct |
249 ms |
26076 KB |
Output is correct |
36 |
Correct |
260 ms |
27280 KB |
Output is correct |
37 |
Correct |
267 ms |
28164 KB |
Output is correct |
38 |
Correct |
248 ms |
27988 KB |
Output is correct |
39 |
Correct |
257 ms |
27900 KB |
Output is correct |
40 |
Correct |
251 ms |
27988 KB |
Output is correct |
41 |
Correct |
260 ms |
27728 KB |
Output is correct |
42 |
Correct |
249 ms |
27984 KB |
Output is correct |
43 |
Correct |
242 ms |
27220 KB |
Output is correct |
44 |
Correct |
250 ms |
27472 KB |
Output is correct |
45 |
Correct |
245 ms |
27680 KB |
Output is correct |
46 |
Correct |
259 ms |
28768 KB |
Output is correct |
47 |
Correct |
120 ms |
23124 KB |
Output is correct |
48 |
Correct |
150 ms |
19168 KB |
Output is correct |
49 |
Correct |
246 ms |
26196 KB |
Output is correct |
50 |
Correct |
147 ms |
20932 KB |
Output is correct |
51 |
Correct |
125 ms |
23264 KB |
Output is correct |
52 |
Correct |
229 ms |
23120 KB |
Output is correct |