#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=2e5+5,tt=19;
ll n,q,s,t,ans=0,a[mxn];
struct segment{
ll val[(1<<tt)];
void add(int id,int L,int R,int l,int r,ll x){
if(L==l && R==r){
val[id]+=x;
return;
}
int mid=(L+R)/2;
if(l<mid)
add(id*2,L,mid,l,min(r,mid),x);
if(r>mid)
add(id*2+1,mid,R,max(l,mid),r,x);
}
ll get(int id,int L,int R,int x){
if(L+1==R)
return val[id];
int mid=(L+R)/2;
if(x<mid)
return get(id*2,L,mid,x)+val[id];
else
return get(id*2+1,mid,R,x)+val[id];
}
}seg;
ll f(ll x,ll y){
if(x>=y)
return (x-y)*t;
return (x-y)*s;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q>>s>>t;
for(int i=0;i<=n;i++){
cin>>a[i];
seg.add(1,0,n+1,i,i+1,a[i]);
}
for(int i=1;i<=n;i++){
ans+=f(a[i-1],a[i]);
}
while(q--){
ll l,r,x,w,z,ww,zz;
cin>>l>>r>>x;
if(l!=0){
w=seg.get(1,0,n+1,l-1);
z=seg.get(1,0,n+1,l);
ans-=f(w,z);
ans+=f(w,z+x);
}
if(r!=n){
ww=seg.get(1,0,n+1,r);
zz=seg.get(1,0,n+1,r+1);
ans-=f(ww,zz);
ans+=f(ww+x,zz);
}
seg.add(1,0,n+1,l,r+1,x);
cout<<ans<<'\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2392 KB |
Output is correct |
2 |
Correct |
2 ms |
2396 KB |
Output is correct |
3 |
Correct |
3 ms |
2524 KB |
Output is correct |
4 |
Correct |
2 ms |
2396 KB |
Output is correct |
5 |
Correct |
2 ms |
2396 KB |
Output is correct |
6 |
Correct |
3 ms |
2392 KB |
Output is correct |
7 |
Correct |
3 ms |
2396 KB |
Output is correct |
8 |
Correct |
3 ms |
2604 KB |
Output is correct |
9 |
Correct |
2 ms |
2396 KB |
Output is correct |
10 |
Correct |
2 ms |
2396 KB |
Output is correct |
11 |
Correct |
2 ms |
2396 KB |
Output is correct |
12 |
Correct |
3 ms |
2600 KB |
Output is correct |
13 |
Correct |
2 ms |
2400 KB |
Output is correct |
14 |
Correct |
2 ms |
2396 KB |
Output is correct |
15 |
Correct |
3 ms |
2396 KB |
Output is correct |
16 |
Correct |
2 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
2 ms |
2524 KB |
Output is correct |
19 |
Correct |
1 ms |
2392 KB |
Output is correct |
20 |
Correct |
1 ms |
2512 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
229 ms |
12860 KB |
Output is correct |
2 |
Correct |
249 ms |
13572 KB |
Output is correct |
3 |
Correct |
216 ms |
14160 KB |
Output is correct |
4 |
Correct |
208 ms |
13352 KB |
Output is correct |
5 |
Correct |
225 ms |
14512 KB |
Output is correct |
6 |
Correct |
116 ms |
13400 KB |
Output is correct |
7 |
Correct |
102 ms |
13396 KB |
Output is correct |
8 |
Correct |
200 ms |
14328 KB |
Output is correct |
9 |
Correct |
183 ms |
14740 KB |
Output is correct |
10 |
Correct |
196 ms |
13476 KB |
Output is correct |
11 |
Correct |
134 ms |
13476 KB |
Output is correct |
12 |
Correct |
100 ms |
14120 KB |
Output is correct |
13 |
Correct |
101 ms |
14364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2392 KB |
Output is correct |
2 |
Correct |
2 ms |
2396 KB |
Output is correct |
3 |
Correct |
3 ms |
2524 KB |
Output is correct |
4 |
Correct |
2 ms |
2396 KB |
Output is correct |
5 |
Correct |
2 ms |
2396 KB |
Output is correct |
6 |
Correct |
3 ms |
2392 KB |
Output is correct |
7 |
Correct |
3 ms |
2396 KB |
Output is correct |
8 |
Correct |
3 ms |
2604 KB |
Output is correct |
9 |
Correct |
2 ms |
2396 KB |
Output is correct |
10 |
Correct |
2 ms |
2396 KB |
Output is correct |
11 |
Correct |
2 ms |
2396 KB |
Output is correct |
12 |
Correct |
3 ms |
2600 KB |
Output is correct |
13 |
Correct |
2 ms |
2400 KB |
Output is correct |
14 |
Correct |
2 ms |
2396 KB |
Output is correct |
15 |
Correct |
3 ms |
2396 KB |
Output is correct |
16 |
Correct |
2 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
2 ms |
2524 KB |
Output is correct |
19 |
Correct |
1 ms |
2392 KB |
Output is correct |
20 |
Correct |
1 ms |
2512 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
22 |
Correct |
229 ms |
12860 KB |
Output is correct |
23 |
Correct |
249 ms |
13572 KB |
Output is correct |
24 |
Correct |
216 ms |
14160 KB |
Output is correct |
25 |
Correct |
208 ms |
13352 KB |
Output is correct |
26 |
Correct |
225 ms |
14512 KB |
Output is correct |
27 |
Correct |
116 ms |
13400 KB |
Output is correct |
28 |
Correct |
102 ms |
13396 KB |
Output is correct |
29 |
Correct |
200 ms |
14328 KB |
Output is correct |
30 |
Correct |
183 ms |
14740 KB |
Output is correct |
31 |
Correct |
196 ms |
13476 KB |
Output is correct |
32 |
Correct |
134 ms |
13476 KB |
Output is correct |
33 |
Correct |
100 ms |
14120 KB |
Output is correct |
34 |
Correct |
101 ms |
14364 KB |
Output is correct |
35 |
Correct |
223 ms |
13068 KB |
Output is correct |
36 |
Correct |
227 ms |
14432 KB |
Output is correct |
37 |
Correct |
236 ms |
15268 KB |
Output is correct |
38 |
Correct |
236 ms |
14960 KB |
Output is correct |
39 |
Correct |
265 ms |
15060 KB |
Output is correct |
40 |
Correct |
227 ms |
15028 KB |
Output is correct |
41 |
Correct |
223 ms |
14932 KB |
Output is correct |
42 |
Correct |
231 ms |
15056 KB |
Output is correct |
43 |
Correct |
229 ms |
14404 KB |
Output is correct |
44 |
Correct |
217 ms |
14676 KB |
Output is correct |
45 |
Correct |
211 ms |
14628 KB |
Output is correct |
46 |
Correct |
229 ms |
15588 KB |
Output is correct |
47 |
Correct |
105 ms |
14076 KB |
Output is correct |
48 |
Correct |
110 ms |
14160 KB |
Output is correct |
49 |
Correct |
207 ms |
13240 KB |
Output is correct |
50 |
Correct |
134 ms |
13888 KB |
Output is correct |
51 |
Correct |
101 ms |
14420 KB |
Output is correct |
52 |
Correct |
132 ms |
14160 KB |
Output is correct |