#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> a;
int st[800002];
int lazy[800002];
void build(int node, int start, int end){
if(start==end){
st[node] = a[start];
return;
}
int mid = (start+end)/2;
build(2*node,start,mid);
build(2*node+1,mid+1,end);
st[node] = st[2*node]+st[2*node+1];
return;
}
void update(int node, int start, int end,int l, int r, int val){
if(lazy[node]){
st[node]+= (end-start+1)*lazy[node];
if(start!=end){
lazy[2*node]+=lazy[node];
lazy[2*node+1]+=lazy[node];
}
lazy[node] =0;
}
if(r<start||l>end||l>r)
return;
if(l==start&&r==end){
st[node]+=(end-start+1)*val;
if(start!=end){
lazy[2*node]+=val;
lazy[2*node+1]+=val;
}
return;
}
int mid = (start+end)/2;
update(2*node, start, mid, l, min(mid,r), val);
update(2*node+1, mid+1, end, max(mid+1,l), r, val);
st[node] = st[2*node]+st[2*node+1];
}
int query(int node, int start, int end, int l, int r){
if(r<start||l>end||l>r)
return 0;
if(lazy[node]){
st[node]+=(end-start+1)*lazy[node];
if(start!=end){
lazy[2*node]+=lazy[node];
lazy[2*node+1]+=lazy[node];
}
lazy[node] =0;
}
if(l==start&&r==end){
return st[node];
}
int mid = (start+end)/2;
int p1 = query(2*node,start,mid,l,min(mid,r));
int p2 = query(2*node+1,mid+1,end,max(mid+1,l),r);
return p1+p2;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,q,s,t;
cin>>n>>q>>s>>t;
a.resize(n+1);
for(int i=0;i<=n;i++) cin>>a[i];
int res = 0;
for(int i=0;i<n;i++)
if(a[i]<a[i+1]) res-=s*(a[i+1]-a[i]);
else res+=t*(a[i]-a[i+1]);
build(1, 0, n);
while(q--){
int l,r,x;
cin>>l>>r>>x;
// l--;
// r--;
if(l>0){
int pl = query(1,0,n,l-1,l-1);
int ll = query(1, 0, n, l, l);
if(pl<ll) res= res+s*(ll-pl);
else if(pl>=ll) res = res-t*(pl-ll);
ll+=x;
if(pl<ll) res-=s*(ll-pl);
else res+=t*(pl-ll);
}
if(r<n)
{
int rr = query(1, 0, n, r, r);
int ar = query(1, 0, n, r+1, r+1);
if(rr<ar) res+=s*(ar-rr);
else res-=t*(rr-ar);
rr+=x;
if(rr<ar) res-=s*(ar-rr);
else res+=t*(rr-ar);
}
update(1, 0, n, l, r, x);
cout<<res<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
6 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
632 KB |
Output is correct |
12 |
Correct |
5 ms |
504 KB |
Output is correct |
13 |
Correct |
4 ms |
376 KB |
Output is correct |
14 |
Correct |
4 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
504 KB |
Output is correct |
16 |
Correct |
4 ms |
504 KB |
Output is correct |
17 |
Correct |
4 ms |
376 KB |
Output is correct |
18 |
Correct |
4 ms |
536 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
534 ms |
11700 KB |
Output is correct |
2 |
Correct |
542 ms |
12296 KB |
Output is correct |
3 |
Correct |
524 ms |
12924 KB |
Output is correct |
4 |
Correct |
543 ms |
12152 KB |
Output is correct |
5 |
Correct |
529 ms |
12920 KB |
Output is correct |
6 |
Correct |
235 ms |
9080 KB |
Output is correct |
7 |
Correct |
245 ms |
8952 KB |
Output is correct |
8 |
Correct |
431 ms |
13084 KB |
Output is correct |
9 |
Correct |
437 ms |
13456 KB |
Output is correct |
10 |
Correct |
435 ms |
12252 KB |
Output is correct |
11 |
Correct |
273 ms |
9048 KB |
Output is correct |
12 |
Correct |
234 ms |
9532 KB |
Output is correct |
13 |
Correct |
230 ms |
9848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
6 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
632 KB |
Output is correct |
12 |
Correct |
5 ms |
504 KB |
Output is correct |
13 |
Correct |
4 ms |
376 KB |
Output is correct |
14 |
Correct |
4 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
504 KB |
Output is correct |
16 |
Correct |
4 ms |
504 KB |
Output is correct |
17 |
Correct |
4 ms |
376 KB |
Output is correct |
18 |
Correct |
4 ms |
536 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
380 KB |
Output is correct |
22 |
Correct |
534 ms |
11700 KB |
Output is correct |
23 |
Correct |
542 ms |
12296 KB |
Output is correct |
24 |
Correct |
524 ms |
12924 KB |
Output is correct |
25 |
Correct |
543 ms |
12152 KB |
Output is correct |
26 |
Correct |
529 ms |
12920 KB |
Output is correct |
27 |
Correct |
235 ms |
9080 KB |
Output is correct |
28 |
Correct |
245 ms |
8952 KB |
Output is correct |
29 |
Correct |
431 ms |
13084 KB |
Output is correct |
30 |
Correct |
437 ms |
13456 KB |
Output is correct |
31 |
Correct |
435 ms |
12252 KB |
Output is correct |
32 |
Correct |
273 ms |
9048 KB |
Output is correct |
33 |
Correct |
234 ms |
9532 KB |
Output is correct |
34 |
Correct |
230 ms |
9848 KB |
Output is correct |
35 |
Correct |
519 ms |
11780 KB |
Output is correct |
36 |
Correct |
523 ms |
13176 KB |
Output is correct |
37 |
Correct |
523 ms |
13944 KB |
Output is correct |
38 |
Correct |
528 ms |
13816 KB |
Output is correct |
39 |
Correct |
535 ms |
13808 KB |
Output is correct |
40 |
Correct |
551 ms |
13880 KB |
Output is correct |
41 |
Correct |
567 ms |
13644 KB |
Output is correct |
42 |
Correct |
536 ms |
13732 KB |
Output is correct |
43 |
Correct |
597 ms |
13048 KB |
Output is correct |
44 |
Correct |
541 ms |
13432 KB |
Output is correct |
45 |
Correct |
519 ms |
13176 KB |
Output is correct |
46 |
Correct |
528 ms |
13808 KB |
Output is correct |
47 |
Correct |
237 ms |
9720 KB |
Output is correct |
48 |
Correct |
261 ms |
9888 KB |
Output is correct |
49 |
Correct |
516 ms |
13048 KB |
Output is correct |
50 |
Correct |
276 ms |
9592 KB |
Output is correct |
51 |
Correct |
238 ms |
9720 KB |
Output is correct |
52 |
Correct |
342 ms |
9708 KB |
Output is correct |