#include <bits/stdc++.h>
using namespace std;
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ii;
typedef int ll;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 220000
ii n, q, s, t, bit[maxn];
void att(ii pos, ii val) {
for(ii i = pos; i <= n && i > 0; i+= i&-i)
bit[i]+= val;
}
ii qrr(ii pos) {
ii sum = 0;
for(ii i = pos; i > 0; i-= i&-i)
sum+= bit[i];
return sum;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
cin >> n >> q >> s >> t;
for(ii i = 0; i <= n; i++) {
ii a; cin >> a;
att(i,a);
att(i+1,-a);
}
ii up = 0;
ii dw = 0;
for(ii i = 1; i <= n; i++) {
ii l1 = qrr(i-1);
ii l2 = qrr(i);
if(l1 < l2) {
up+= abs(l1-l2);
}
else {
dw+= abs(l1-l2);
}
}
while(q--) {
ii l, r, x;
cin >> l >> r >> x;
ii l1 = qrr(l-1);
ii l2 = qrr(l);
if(l1 < l2) {
up-= abs(l1-l2);
}
else {
dw-= abs(l1-l2);
}
ii r1 = qrr(r);
ii r2 = qrr(r+1);
if(r1 < r2 && r != n) {
up-= abs(r1-r2);
}
else if(r != n) {
dw-= abs(r1-r2);
}
att(l,x);
att(r+1,-x);
l1 = qrr(l-1);
l2 = qrr(l);
if(l1 < l2) {
up+= abs(l1-l2);
}
else {
dw+= abs(l1-l2);
}
r1 = qrr(r);
r2 = qrr(r+1);
if(r1 < r2 && r != n) {
up+= abs(r1-r2);
}
else if(r != n) {
dw+= abs(r1-r2);
}
cout << dw*t - up*s << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
2 ms |
332 KB |
Output is correct |
8 |
Correct |
2 ms |
416 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
2 ms |
332 KB |
Output is correct |
12 |
Correct |
2 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
368 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
3220 KB |
Output is correct |
2 |
Correct |
146 ms |
3976 KB |
Output is correct |
3 |
Correct |
159 ms |
4564 KB |
Output is correct |
4 |
Correct |
156 ms |
4644 KB |
Output is correct |
5 |
Correct |
149 ms |
5444 KB |
Output is correct |
6 |
Correct |
117 ms |
5856 KB |
Output is correct |
7 |
Correct |
110 ms |
5832 KB |
Output is correct |
8 |
Correct |
189 ms |
5696 KB |
Output is correct |
9 |
Correct |
150 ms |
6084 KB |
Output is correct |
10 |
Correct |
148 ms |
4764 KB |
Output is correct |
11 |
Correct |
127 ms |
5780 KB |
Output is correct |
12 |
Correct |
134 ms |
6260 KB |
Output is correct |
13 |
Correct |
115 ms |
6596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
2 ms |
332 KB |
Output is correct |
8 |
Correct |
2 ms |
416 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
2 ms |
332 KB |
Output is correct |
12 |
Correct |
2 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
368 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
153 ms |
3220 KB |
Output is correct |
23 |
Correct |
146 ms |
3976 KB |
Output is correct |
24 |
Correct |
159 ms |
4564 KB |
Output is correct |
25 |
Correct |
156 ms |
4644 KB |
Output is correct |
26 |
Correct |
149 ms |
5444 KB |
Output is correct |
27 |
Correct |
117 ms |
5856 KB |
Output is correct |
28 |
Correct |
110 ms |
5832 KB |
Output is correct |
29 |
Correct |
189 ms |
5696 KB |
Output is correct |
30 |
Correct |
150 ms |
6084 KB |
Output is correct |
31 |
Correct |
148 ms |
4764 KB |
Output is correct |
32 |
Correct |
127 ms |
5780 KB |
Output is correct |
33 |
Correct |
134 ms |
6260 KB |
Output is correct |
34 |
Correct |
115 ms |
6596 KB |
Output is correct |
35 |
Correct |
174 ms |
4420 KB |
Output is correct |
36 |
Correct |
182 ms |
5828 KB |
Output is correct |
37 |
Correct |
185 ms |
6640 KB |
Output is correct |
38 |
Correct |
159 ms |
6400 KB |
Output is correct |
39 |
Correct |
153 ms |
6468 KB |
Output is correct |
40 |
Correct |
153 ms |
6508 KB |
Output is correct |
41 |
Correct |
162 ms |
6212 KB |
Output is correct |
42 |
Correct |
166 ms |
6468 KB |
Output is correct |
43 |
Correct |
159 ms |
5700 KB |
Output is correct |
44 |
Correct |
168 ms |
6088 KB |
Output is correct |
45 |
Correct |
155 ms |
5828 KB |
Output is correct |
46 |
Correct |
157 ms |
6436 KB |
Output is correct |
47 |
Correct |
115 ms |
6468 KB |
Output is correct |
48 |
Correct |
136 ms |
6692 KB |
Output is correct |
49 |
Correct |
134 ms |
5628 KB |
Output is correct |
50 |
Correct |
114 ms |
6376 KB |
Output is correct |
51 |
Correct |
112 ms |
6472 KB |
Output is correct |
52 |
Correct |
121 ms |
6384 KB |
Output is correct |