This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
using namespace std;
long long tree[800'007];
void UpdateTree(long long v, long long l, long long r, long long vl, long long vr, long long val){
if (vl>r||vr<l) return;
if (vl>=l&&vr<=r){
tree[v]+=val;
return;
}
long long mid=(vl+vr)/2;
UpdateTree(2*v, l, r, vl, mid, val);
UpdateTree(2*v+1, l, r, mid+1, vr, val);
}
long long GetTree(long long v){
long long out=0;
while (v>0){
out+=tree[v];
v>>=1;
}
return out;
}
long long temps[800'007];
void UpdateTemps(long long v, long long l, long long r, long long vl, long long vr, long long val){
if (vl>r||vr<l) return;
if (vl>=l&&vr<=r){
temps[v]+=val;
return;
}
long long mid=(vl+vr)/2;
UpdateTemps(2*v, l, r, vl, mid, val);
UpdateTemps(2*v+1, l, r, mid+1, vr, val);
}
long long GetTemps(long long v){
long long out=0;
while (v>0){
out+=temps[v];
v>>=1;
}
return out;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (long long i=0;i<400'007;i++) tree[i]=0;
for (long long i=0;i<400'007;i++) temps[i]=0;
long long n, q, s, t;
cin>>n>>q>>s>>t;
long long trsize=1;
while (trsize<n+1) trsize<<=1;
for (long long i=0;i<=n;i++){
cin>>tree[trsize+i];
}
for (long long i=1;i<n+1;i++){
temps[trsize+i]=temps[trsize+i-1];
if (tree[trsize+i]>tree[trsize+i-1]) temps[trsize+i]-=s*(tree[trsize+i]-tree[trsize+i-1]);
else temps[trsize+i]+=t*(tree[trsize+i-1]-tree[trsize+i]);
}
// for (long long i=trsize;i<2*trsize;i++) cout<<GetTemps(i)<<" ";
// cout<<'\n';
for (long long qe=0;qe<q;qe++){
long long l, r, x;
cin>>l>>r>>x;
UpdateTree(1, trsize+l, trsize+r, trsize, 2*trsize-1, x);
if (l>0){
long long preBorder=GetTree(trsize+l-1), postBorder=GetTree(trsize+l);
if (preBorder>=postBorder&&preBorder>=postBorder-x){
UpdateTemps(1, trsize+l, 2*trsize-1, trsize, 2*trsize-1, -t*x);
}
else if (preBorder<postBorder&&preBorder<postBorder-x){
UpdateTemps(1, trsize+l, 2*trsize-1, trsize, 2*trsize-1, -s*x);
}
else if (preBorder<postBorder&&preBorder>=postBorder-x){
UpdateTemps(1, trsize+l, 2*trsize-1, trsize, 2*trsize-1, -t*(preBorder-postBorder+x)+(-s)*(postBorder-preBorder));
}
else{
UpdateTemps(1, trsize+l, 2*trsize-1, trsize, 2*trsize-1, s*(postBorder-x-preBorder)+t*(postBorder-preBorder));
}
}
if (r<n){
long long preBorder=GetTree(trsize+r), postBorder=GetTree(trsize+r+1);
if (preBorder>=postBorder&&preBorder-x>=postBorder){
UpdateTemps(1, trsize+r+1, 2*trsize-1, trsize, 2*trsize-1, t*x);
}
else if (preBorder<postBorder&&preBorder-x<postBorder){
UpdateTemps(1, trsize+r+1, 2*trsize-1, trsize, 2*trsize-1, s*x);
}
else if (preBorder<postBorder&&preBorder-x>=postBorder){
UpdateTemps(1, trsize+r+1, 2*trsize-1, trsize, 2*trsize-1, -t*(preBorder-x-postBorder)+s*(postBorder-preBorder));
}
else{
UpdateTemps(1, trsize+r+1, 2*trsize-1, trsize, 2*trsize-1, s*(postBorder-preBorder+x)-t*(preBorder-postBorder));
}
}
// for (long long i=trsize;i<trsize+n+1;i++) cout<<GetTree(i)<<" ";
// cout<<'\n';
// for (long long i=trsize;i<trsize+n+1;i++) cout<<GetTemps(i)<<" ";
// cout<<'\n';
cout<<GetTemps(trsize+n)<<'\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |