#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>st(8*200000);
vector<int>lazy(8*200000);
int l,r,x;
int query(int i, int j, int p) {
if(i > l || j < l)
return 0;
if(i == j) {
st[p] += lazy[p];
lazy[p] = 0;
return st[p];
}
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
lazy[p] = 0;
int mid = (i+j)/2;
return query(i, mid, 2*p) + query(mid+1, j, 2*p+1);
}
void update(int i, int j, int p) {
if(i > r || j < l)
return;
if(i >= l && j <= r) {
lazy[p] += x;
return;
}
int mid = (i+j)/2;
update(i, mid, 2*p);
update(mid+1, j, 2*p+1);
}
signed main() {
int n,q,s,t; cin>>n>>q>>s>>t;
vector<int>v(n+1);
for(auto &z : v)
cin>>z;
long long ans = 0;
for(int i = 1 ; i <= n ; i++) {
x = v[i];
l = r = i;
update(1, n, 1);
if(v[i] > v[i-1])
ans -= (v[i]-v[i-1]) * s;
else
ans += (v[i-1]-v[i]) * t;
}
while(q--) {
cin>>l>>r>>x;
int L = l, R = r;
int A = query(1, n, 1);
l = R;
int B = query(1, n, 1);
l = L-1;
int a = (l == 0 ? 0 : query(1, n, 1));
l = R+1;
int b = (l == n+1 ? 0 : query(1, n, 1));
l = L, r = R;
update(1, n, 1);
l = L;
int nwA = query(1, n, 1);
l = R;
int nwB = query(1, n, 1);
if(A >= a)
ans += (A - a) * s;
else
ans -= (a - A) * t;
if(nwA >= a)
ans -= (nwA - a) * s;
else
ans += (a - nwA) * t;
if(R < n) {
if(b >= B)
ans += (b - B) * s;
else
ans -= (B - b) * t;
if(b >= nwB)
ans -= (b - nwB) * s;
else
ans += (nwB - b) * t;
}
cout << ans << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
25376 KB |
Output is correct |
2 |
Correct |
17 ms |
25452 KB |
Output is correct |
3 |
Correct |
17 ms |
25424 KB |
Output is correct |
4 |
Correct |
18 ms |
25428 KB |
Output is correct |
5 |
Correct |
17 ms |
25448 KB |
Output is correct |
6 |
Correct |
17 ms |
25332 KB |
Output is correct |
7 |
Correct |
17 ms |
25388 KB |
Output is correct |
8 |
Correct |
17 ms |
25376 KB |
Output is correct |
9 |
Correct |
17 ms |
25428 KB |
Output is correct |
10 |
Correct |
19 ms |
25444 KB |
Output is correct |
11 |
Correct |
17 ms |
25468 KB |
Output is correct |
12 |
Correct |
17 ms |
25464 KB |
Output is correct |
13 |
Correct |
17 ms |
25428 KB |
Output is correct |
14 |
Correct |
17 ms |
25448 KB |
Output is correct |
15 |
Correct |
18 ms |
25452 KB |
Output is correct |
16 |
Correct |
17 ms |
25428 KB |
Output is correct |
17 |
Correct |
15 ms |
25428 KB |
Output is correct |
18 |
Correct |
16 ms |
25380 KB |
Output is correct |
19 |
Correct |
12 ms |
25364 KB |
Output is correct |
20 |
Correct |
10 ms |
25300 KB |
Output is correct |
21 |
Correct |
10 ms |
25300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
796 ms |
28808 KB |
Output is correct |
2 |
Correct |
836 ms |
29200 KB |
Output is correct |
3 |
Correct |
822 ms |
29780 KB |
Output is correct |
4 |
Correct |
800 ms |
34364 KB |
Output is correct |
5 |
Correct |
822 ms |
35492 KB |
Output is correct |
6 |
Correct |
559 ms |
34636 KB |
Output is correct |
7 |
Correct |
561 ms |
34484 KB |
Output is correct |
8 |
Correct |
819 ms |
35324 KB |
Output is correct |
9 |
Correct |
765 ms |
35660 KB |
Output is correct |
10 |
Correct |
744 ms |
34364 KB |
Output is correct |
11 |
Correct |
602 ms |
34552 KB |
Output is correct |
12 |
Correct |
570 ms |
35204 KB |
Output is correct |
13 |
Correct |
603 ms |
35300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
25376 KB |
Output is correct |
2 |
Correct |
17 ms |
25452 KB |
Output is correct |
3 |
Correct |
17 ms |
25424 KB |
Output is correct |
4 |
Correct |
18 ms |
25428 KB |
Output is correct |
5 |
Correct |
17 ms |
25448 KB |
Output is correct |
6 |
Correct |
17 ms |
25332 KB |
Output is correct |
7 |
Correct |
17 ms |
25388 KB |
Output is correct |
8 |
Correct |
17 ms |
25376 KB |
Output is correct |
9 |
Correct |
17 ms |
25428 KB |
Output is correct |
10 |
Correct |
19 ms |
25444 KB |
Output is correct |
11 |
Correct |
17 ms |
25468 KB |
Output is correct |
12 |
Correct |
17 ms |
25464 KB |
Output is correct |
13 |
Correct |
17 ms |
25428 KB |
Output is correct |
14 |
Correct |
17 ms |
25448 KB |
Output is correct |
15 |
Correct |
18 ms |
25452 KB |
Output is correct |
16 |
Correct |
17 ms |
25428 KB |
Output is correct |
17 |
Correct |
15 ms |
25428 KB |
Output is correct |
18 |
Correct |
16 ms |
25380 KB |
Output is correct |
19 |
Correct |
12 ms |
25364 KB |
Output is correct |
20 |
Correct |
10 ms |
25300 KB |
Output is correct |
21 |
Correct |
10 ms |
25300 KB |
Output is correct |
22 |
Correct |
796 ms |
28808 KB |
Output is correct |
23 |
Correct |
836 ms |
29200 KB |
Output is correct |
24 |
Correct |
822 ms |
29780 KB |
Output is correct |
25 |
Correct |
800 ms |
34364 KB |
Output is correct |
26 |
Correct |
822 ms |
35492 KB |
Output is correct |
27 |
Correct |
559 ms |
34636 KB |
Output is correct |
28 |
Correct |
561 ms |
34484 KB |
Output is correct |
29 |
Correct |
819 ms |
35324 KB |
Output is correct |
30 |
Correct |
765 ms |
35660 KB |
Output is correct |
31 |
Correct |
744 ms |
34364 KB |
Output is correct |
32 |
Correct |
602 ms |
34552 KB |
Output is correct |
33 |
Correct |
570 ms |
35204 KB |
Output is correct |
34 |
Correct |
603 ms |
35300 KB |
Output is correct |
35 |
Correct |
789 ms |
33936 KB |
Output is correct |
36 |
Correct |
797 ms |
35332 KB |
Output is correct |
37 |
Correct |
799 ms |
36220 KB |
Output is correct |
38 |
Correct |
795 ms |
35828 KB |
Output is correct |
39 |
Correct |
806 ms |
36024 KB |
Output is correct |
40 |
Correct |
798 ms |
35816 KB |
Output is correct |
41 |
Correct |
795 ms |
35792 KB |
Output is correct |
42 |
Correct |
797 ms |
35956 KB |
Output is correct |
43 |
Correct |
820 ms |
35180 KB |
Output is correct |
44 |
Correct |
797 ms |
35480 KB |
Output is correct |
45 |
Correct |
796 ms |
35484 KB |
Output is correct |
46 |
Correct |
823 ms |
36892 KB |
Output is correct |
47 |
Correct |
559 ms |
35136 KB |
Output is correct |
48 |
Correct |
591 ms |
35212 KB |
Output is correct |
49 |
Correct |
761 ms |
34208 KB |
Output is correct |
50 |
Correct |
600 ms |
34936 KB |
Output is correct |
51 |
Correct |
572 ms |
35404 KB |
Output is correct |
52 |
Correct |
647 ms |
35228 KB |
Output is correct |