#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q, s, t, v[200002];
ll ts;
ll aib[200002];
void add(int nod, int val)
{
for(; nod <= n; nod += (nod & (-nod)))
aib[nod] += val;
}
ll compute(int nod)
{
ll ans = 0;
for(; nod; nod -= (nod & (-nod)))
ans += aib[nod];
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q >> s >> t;
for(int i = 0; i <= n; ++i)
cin >> v[i];
for(int i = 0; i < n; ++i)
if(v[i] < v[i+1])
ts = ts - 1LL * s * (v[i+1] - v[i]);
else
ts = ts + 1LL * t * (v[i] - v[i+1]);
for(; q; --q)
{
int st, dr, val;
cin >> st >> dr >> val;
if(v[st - 1] + compute(st - 1) < v[st] + compute(st))
ts = ts + 1LL * s * (v[st] + compute(st) - v[st - 1] - compute(st - 1));
else
ts = ts - 1LL * t * (v[st - 1] + compute(st - 1) - v[st] - compute(st));
if(dr != n)
{
if(v[dr] + compute(dr) < v[dr + 1] + compute(dr + 1))
ts = ts + 1LL * s * (v[dr + 1] + compute(dr + 1) - v[dr] - compute(dr));
else
ts = ts - 1LL * t * (v[dr] + compute(dr) - v[dr + 1] - compute(dr + 1));
}
add(st, val);
add(dr + 1, -val);
if(v[st - 1] + compute(st - 1) < v[st] + compute(st))
ts = ts - 1LL * s * (v[st] + compute(st) - v[st - 1] - compute(st - 1));
else
ts = ts + 1LL * t * (v[st - 1] + compute(st - 1) - v[st] - compute(st));
if(dr != n)
{
if(v[dr] + compute(dr) < v[dr + 1] + compute(dr + 1))
ts = ts - 1LL * s * (v[dr + 1] + compute(dr + 1) - v[dr] - compute(dr));
else
ts = ts + 1LL * t * (v[dr] + compute(dr) - v[dr + 1] - compute(dr + 1));
}
cout << ts << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
504 KB |
Output is correct |
3 |
Correct |
7 ms |
504 KB |
Output is correct |
4 |
Correct |
6 ms |
508 KB |
Output is correct |
5 |
Correct |
7 ms |
504 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
6 ms |
504 KB |
Output is correct |
8 |
Correct |
7 ms |
504 KB |
Output is correct |
9 |
Correct |
7 ms |
504 KB |
Output is correct |
10 |
Correct |
7 ms |
504 KB |
Output is correct |
11 |
Correct |
7 ms |
412 KB |
Output is correct |
12 |
Correct |
6 ms |
504 KB |
Output is correct |
13 |
Correct |
6 ms |
504 KB |
Output is correct |
14 |
Correct |
6 ms |
504 KB |
Output is correct |
15 |
Correct |
7 ms |
504 KB |
Output is correct |
16 |
Correct |
6 ms |
508 KB |
Output is correct |
17 |
Correct |
6 ms |
504 KB |
Output is correct |
18 |
Correct |
6 ms |
504 KB |
Output is correct |
19 |
Correct |
5 ms |
248 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
193 ms |
9592 KB |
Output is correct |
2 |
Correct |
195 ms |
10104 KB |
Output is correct |
3 |
Correct |
209 ms |
10688 KB |
Output is correct |
4 |
Correct |
183 ms |
10104 KB |
Output is correct |
5 |
Correct |
191 ms |
11292 KB |
Output is correct |
6 |
Correct |
123 ms |
8824 KB |
Output is correct |
7 |
Correct |
134 ms |
8824 KB |
Output is correct |
8 |
Correct |
180 ms |
11132 KB |
Output is correct |
9 |
Correct |
183 ms |
11384 KB |
Output is correct |
10 |
Correct |
174 ms |
10232 KB |
Output is correct |
11 |
Correct |
134 ms |
8696 KB |
Output is correct |
12 |
Correct |
122 ms |
9468 KB |
Output is correct |
13 |
Correct |
131 ms |
9592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
504 KB |
Output is correct |
3 |
Correct |
7 ms |
504 KB |
Output is correct |
4 |
Correct |
6 ms |
508 KB |
Output is correct |
5 |
Correct |
7 ms |
504 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
6 ms |
504 KB |
Output is correct |
8 |
Correct |
7 ms |
504 KB |
Output is correct |
9 |
Correct |
7 ms |
504 KB |
Output is correct |
10 |
Correct |
7 ms |
504 KB |
Output is correct |
11 |
Correct |
7 ms |
412 KB |
Output is correct |
12 |
Correct |
6 ms |
504 KB |
Output is correct |
13 |
Correct |
6 ms |
504 KB |
Output is correct |
14 |
Correct |
6 ms |
504 KB |
Output is correct |
15 |
Correct |
7 ms |
504 KB |
Output is correct |
16 |
Correct |
6 ms |
508 KB |
Output is correct |
17 |
Correct |
6 ms |
504 KB |
Output is correct |
18 |
Correct |
6 ms |
504 KB |
Output is correct |
19 |
Correct |
5 ms |
248 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
193 ms |
9592 KB |
Output is correct |
23 |
Correct |
195 ms |
10104 KB |
Output is correct |
24 |
Correct |
209 ms |
10688 KB |
Output is correct |
25 |
Correct |
183 ms |
10104 KB |
Output is correct |
26 |
Correct |
191 ms |
11292 KB |
Output is correct |
27 |
Correct |
123 ms |
8824 KB |
Output is correct |
28 |
Correct |
134 ms |
8824 KB |
Output is correct |
29 |
Correct |
180 ms |
11132 KB |
Output is correct |
30 |
Correct |
183 ms |
11384 KB |
Output is correct |
31 |
Correct |
174 ms |
10232 KB |
Output is correct |
32 |
Correct |
134 ms |
8696 KB |
Output is correct |
33 |
Correct |
122 ms |
9468 KB |
Output is correct |
34 |
Correct |
131 ms |
9592 KB |
Output is correct |
35 |
Correct |
198 ms |
9696 KB |
Output is correct |
36 |
Correct |
217 ms |
11128 KB |
Output is correct |
37 |
Correct |
218 ms |
12024 KB |
Output is correct |
38 |
Correct |
201 ms |
11644 KB |
Output is correct |
39 |
Correct |
204 ms |
11768 KB |
Output is correct |
40 |
Correct |
199 ms |
11640 KB |
Output is correct |
41 |
Correct |
200 ms |
11512 KB |
Output is correct |
42 |
Correct |
199 ms |
11640 KB |
Output is correct |
43 |
Correct |
193 ms |
10872 KB |
Output is correct |
44 |
Correct |
205 ms |
11256 KB |
Output is correct |
45 |
Correct |
185 ms |
11384 KB |
Output is correct |
46 |
Correct |
198 ms |
12408 KB |
Output is correct |
47 |
Correct |
128 ms |
9464 KB |
Output is correct |
48 |
Correct |
141 ms |
9468 KB |
Output is correct |
49 |
Correct |
179 ms |
9976 KB |
Output is correct |
50 |
Correct |
135 ms |
9208 KB |
Output is correct |
51 |
Correct |
124 ms |
9720 KB |
Output is correct |
52 |
Correct |
146 ms |
9464 KB |
Output is correct |