#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>pii;
inline int combine(int a, int b){
return a+b;
}
const int defval=0;
#define lazyChange (e-s+1)
struct node{
int s,e,m;
node *l, *r;
int v;
int lazyUpd, lazySet;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(defval),lazyUpd(0){
if(s!=e){
l=new node(s,m); r=new node(m+1,e);
}
}
inline int forceProp(){
if(s==e){
v+=lazyUpd; lazyUpd=0; return v;
}
if(lazyUpd!=0){
v+=lazyChange*lazyUpd,l->lazyUpd+=lazyUpd,r->lazyUpd+=lazyUpd,lazyUpd=0;
}
return v;
}
void rangeUpd(int first, int last, int c){
if(first<=s&&last>=e){
lazyUpd+=c;
return;
}
forceProp();
if(first<=m)l->rangeUpd(first,last,c);
if(last>m)r->rangeUpd(first,last,c);
v=combine(l->forceProp(),r->forceProp());
}
int query(int x, int y){
if(s==e){
v+=lazyUpd;
lazyUpd=0;
return v;
}
if(x<=s&&y>=e){
forceProp();
return v;
}
forceProp();
if(y<=m)return l->query(x,y);
if(x>m)return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,q,s,t;
cin >> n >> q >> s >> t;
node st(0,n+5);
//node ans(0,n+5);
int ans[n+5];
memset(ans,0,sizeof(ans));
for(int x=0;x<=n;x++){
int temp;
cin >> temp;
st.rangeUpd(x,x,temp);
}
int counter=0;
for(int x=1;x<=n;x++){
int hold=st.query(x,x);
int hold2=st.query(x-1,x-1);
if(hold2<hold){
//ans.rangeUpd(x,x,-1LL*s*abs(hold-hold2));
ans[x]=-1LL*s*abs(hold-hold2);
}
else{
//ans.rangeUpd(x,x,t*abs(hold-hold2));
ans[x]=t*abs(hold-hold2);
}
counter+=ans[x];
}
int l,r,val;
for(int x=0;x<q;x++){
cin >> l >> r >> val;
st.rangeUpd(l,r,val);
//changes
//left
//int hold=ans.query(l,l);
int hold2=st.query(l,l);
int hold3=st.query(l-1,l-1);
if(hold3<hold2){
//ans.rangeUpd(l,l,-hold-1LL*s*abs(hold2-hold3));
counter-=ans[l];
ans[l]=-1LL*s*abs(hold2-hold3);
counter+=ans[l];
}
else{
//ans.rangeUpd(l,l,-hold+t*abs(hold2-hold3));
counter-=ans[l];
ans[l]=t*abs(hold2-hold3);
counter+=ans[l];
}
if(r!=n){
int hold4=st.query(r,r);
int hold5=st.query(r+1,r+1);
//int hold6=ans.query(r+1,r+1);
if(hold4<hold5){
//ans.rangeUpd(r+1,r+1,-hold6-1LL*s*abs(hold4-hold5));
counter-=ans[r+1];
ans[r+1]=-1LL*s*abs(hold4-hold5);
counter+=ans[r+1];
}
else{
//ans.rangeUpd(r+1,r+1,-hold6+t*abs(hold4-hold5));
counter-=ans[r+1];
ans[r+1]=t*abs(hold4-hold5);
counter+=ans[r+1];
}
}
//cout << ans.query(0,n) << "\n";
cout << counter << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
640 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
5 ms |
648 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
3 ms |
596 KB |
Output is correct |
13 |
Correct |
2 ms |
596 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
15 |
Correct |
3 ms |
596 KB |
Output is correct |
16 |
Correct |
2 ms |
596 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
585 ms |
34592 KB |
Output is correct |
2 |
Correct |
596 ms |
40744 KB |
Output is correct |
3 |
Correct |
606 ms |
41200 KB |
Output is correct |
4 |
Correct |
653 ms |
40516 KB |
Output is correct |
5 |
Correct |
639 ms |
41736 KB |
Output is correct |
6 |
Correct |
273 ms |
40804 KB |
Output is correct |
7 |
Correct |
265 ms |
40700 KB |
Output is correct |
8 |
Correct |
544 ms |
41580 KB |
Output is correct |
9 |
Correct |
517 ms |
41800 KB |
Output is correct |
10 |
Correct |
539 ms |
40608 KB |
Output is correct |
11 |
Correct |
238 ms |
40668 KB |
Output is correct |
12 |
Correct |
270 ms |
41420 KB |
Output is correct |
13 |
Correct |
270 ms |
41580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
640 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
5 ms |
648 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
3 ms |
596 KB |
Output is correct |
13 |
Correct |
2 ms |
596 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
15 |
Correct |
3 ms |
596 KB |
Output is correct |
16 |
Correct |
2 ms |
596 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
585 ms |
34592 KB |
Output is correct |
23 |
Correct |
596 ms |
40744 KB |
Output is correct |
24 |
Correct |
606 ms |
41200 KB |
Output is correct |
25 |
Correct |
653 ms |
40516 KB |
Output is correct |
26 |
Correct |
639 ms |
41736 KB |
Output is correct |
27 |
Correct |
273 ms |
40804 KB |
Output is correct |
28 |
Correct |
265 ms |
40700 KB |
Output is correct |
29 |
Correct |
544 ms |
41580 KB |
Output is correct |
30 |
Correct |
517 ms |
41800 KB |
Output is correct |
31 |
Correct |
539 ms |
40608 KB |
Output is correct |
32 |
Correct |
238 ms |
40668 KB |
Output is correct |
33 |
Correct |
270 ms |
41420 KB |
Output is correct |
34 |
Correct |
270 ms |
41580 KB |
Output is correct |
35 |
Correct |
605 ms |
40064 KB |
Output is correct |
36 |
Correct |
655 ms |
41528 KB |
Output is correct |
37 |
Correct |
648 ms |
42380 KB |
Output is correct |
38 |
Correct |
616 ms |
42188 KB |
Output is correct |
39 |
Correct |
594 ms |
42192 KB |
Output is correct |
40 |
Correct |
611 ms |
42128 KB |
Output is correct |
41 |
Correct |
618 ms |
42088 KB |
Output is correct |
42 |
Correct |
614 ms |
42144 KB |
Output is correct |
43 |
Correct |
602 ms |
41292 KB |
Output is correct |
44 |
Correct |
609 ms |
41712 KB |
Output is correct |
45 |
Correct |
618 ms |
41736 KB |
Output is correct |
46 |
Correct |
600 ms |
42816 KB |
Output is correct |
47 |
Correct |
276 ms |
41480 KB |
Output is correct |
48 |
Correct |
204 ms |
41420 KB |
Output is correct |
49 |
Correct |
589 ms |
40588 KB |
Output is correct |
50 |
Correct |
239 ms |
41292 KB |
Output is correct |
51 |
Correct |
270 ms |
41552 KB |
Output is correct |
52 |
Correct |
278 ms |
41324 KB |
Output is correct |