#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 17;
struct fentree {
ll sz;
vector<ll> val;
void init(ll n){
sz = n;
val.assign(sz , 0);
return;
}
void add(ll i , ll k){
ll h = i;
while(h < sz){
val[h] += k;
h |= (h + 1);
}
return;
}
ll cal(ll i){
ll h = i , res = 0;
while(~h){
res += val[h];
h &= (h + 1); h--;
}
return res;
}
};
ll n , q , s , t;
fentree ft;
ll a[maxn];
ll dif(ll a , ll b){
return (b > a ? s : t) * (a - b);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>q>>s>>t;
for(ll i = 0 ; i <= n ; i++){
cin>>a[i];
}
ft.init(n + 1);
for(ll i = 1 ; i <= n ; i++){
ft.add(i , a[i] - a[i - 1]);
}
ll res = 0;
for(ll i = 1 ; i <= n ; i++){
res += dif(a[i - 1] , a[i]);
}
for(ll e = 0 ; e < q ; e++){
ll l , r , k;
cin>>l>>r>>k;
ll hl = ft.cal(l - 1) , hr = ft.cal(l);
ll pr = dif(hl , hr) , cur = dif(hl , hr + k);
res += cur - pr;
if(r < n){
hl = ft.cal(r); hr = ft.cal(r + 1);
pr = dif(hl , hr); cur = dif(hl + k , hr);
res += cur - pr;
}
ft.add(l , k); ft.add(r + 1 , -k);
cout<<res<<'\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
408 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
2 ms |
360 KB |
Output is correct |
15 |
Correct |
1 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
10320 KB |
Output is correct |
2 |
Correct |
105 ms |
10852 KB |
Output is correct |
3 |
Correct |
109 ms |
11488 KB |
Output is correct |
4 |
Correct |
107 ms |
10776 KB |
Output is correct |
5 |
Correct |
107 ms |
12044 KB |
Output is correct |
6 |
Correct |
81 ms |
10968 KB |
Output is correct |
7 |
Correct |
82 ms |
10956 KB |
Output is correct |
8 |
Correct |
113 ms |
11748 KB |
Output is correct |
9 |
Correct |
102 ms |
12320 KB |
Output is correct |
10 |
Correct |
99 ms |
10812 KB |
Output is correct |
11 |
Correct |
86 ms |
10900 KB |
Output is correct |
12 |
Correct |
81 ms |
11628 KB |
Output is correct |
13 |
Correct |
81 ms |
11852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
408 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
2 ms |
360 KB |
Output is correct |
15 |
Correct |
1 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
328 KB |
Output is correct |
22 |
Correct |
114 ms |
10320 KB |
Output is correct |
23 |
Correct |
105 ms |
10852 KB |
Output is correct |
24 |
Correct |
109 ms |
11488 KB |
Output is correct |
25 |
Correct |
107 ms |
10776 KB |
Output is correct |
26 |
Correct |
107 ms |
12044 KB |
Output is correct |
27 |
Correct |
81 ms |
10968 KB |
Output is correct |
28 |
Correct |
82 ms |
10956 KB |
Output is correct |
29 |
Correct |
113 ms |
11748 KB |
Output is correct |
30 |
Correct |
102 ms |
12320 KB |
Output is correct |
31 |
Correct |
99 ms |
10812 KB |
Output is correct |
32 |
Correct |
86 ms |
10900 KB |
Output is correct |
33 |
Correct |
81 ms |
11628 KB |
Output is correct |
34 |
Correct |
81 ms |
11852 KB |
Output is correct |
35 |
Correct |
111 ms |
10360 KB |
Output is correct |
36 |
Correct |
110 ms |
11816 KB |
Output is correct |
37 |
Correct |
108 ms |
12644 KB |
Output is correct |
38 |
Correct |
107 ms |
12464 KB |
Output is correct |
39 |
Correct |
112 ms |
12356 KB |
Output is correct |
40 |
Correct |
106 ms |
12364 KB |
Output is correct |
41 |
Correct |
110 ms |
12232 KB |
Output is correct |
42 |
Correct |
121 ms |
12452 KB |
Output is correct |
43 |
Correct |
110 ms |
11644 KB |
Output is correct |
44 |
Correct |
113 ms |
11980 KB |
Output is correct |
45 |
Correct |
126 ms |
12000 KB |
Output is correct |
46 |
Correct |
115 ms |
13132 KB |
Output is correct |
47 |
Correct |
83 ms |
11696 KB |
Output is correct |
48 |
Correct |
101 ms |
11716 KB |
Output is correct |
49 |
Correct |
98 ms |
10632 KB |
Output is correct |
50 |
Correct |
86 ms |
11468 KB |
Output is correct |
51 |
Correct |
81 ms |
11792 KB |
Output is correct |
52 |
Correct |
87 ms |
11624 KB |
Output is correct |