이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |