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 <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=2e5+5;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
long long segtree[nax*4];
long long tab[nax];
void build(int pos,int l,int r){
if(l==r){
segtree[pos]=tab[l];
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
return;
}
void update(int pos,int l,int r,int left,int right,int value){
if(l>r||l>right||r<left) return;
if(l>=left&&r<=right){
segtree[pos]+=value;
return;
}
int mid=(r+l)/2;
update(pos*2+1,l,mid,left,right,value);
update(pos*2+2,mid+1,r,left,right,value);
return;
}
long long query(int pos,int l,int r,int idx){
if(l==r) return segtree[pos];
int mid=(r+l)/2;
if(idx<=mid) return segtree[pos]+query(pos*2+1,l,mid,idx);
else return segtree[pos]+query(pos*2+2,mid+1,r,idx);
}
int main()
{
optimise;
int n,q,s,t;
cin>>n>>q>>s>>t;
for (int i = 0; i <= n; ++i)
{
cin>>tab[i];
}
build(0,0,n);
long long sum=0;
for (int i = 1; i <= n; ++i)
{
if(tab[i-1]<tab[i]) sum+=1ll*s*(tab[i-1]-tab[i]);
else sum+=1ll*t*(tab[i-1]-tab[i]);
}
while(q--){
int l,r,x;
cin>>l>>r>>x;
int left=query(0,0,n,l);
int lefty=query(0,0,n,l-1);
int right=query(0,0,n,r);
int righty;
if(r<n) righty=query(0,0,n,r+1);
update(0,0,n,l,r,x);
if(lefty<left) sum-=1ll*s*(lefty-left);
else sum-=1ll*t*(lefty-left);
int cnt=query(0,0,n,l);
if(lefty<cnt) sum+=1ll*s*(lefty-cnt);
else sum+=1ll*t*(lefty-cnt);
if(r<n){
cnt=query(0,0,n,r);
if(right<righty) sum-=1ll*s*(right-righty);
else sum-=1ll*t*(right-righty);
if(cnt<righty) sum+=1ll*s*(cnt-righty);
else sum+=1ll*t*(cnt-righty);
}
cout <<sum<<endl;
/*if(tab[l-1]<tab[l]) sum+=1ll*s*(tab[l-1]-tab[l]);
else sum+=1ll*t*(tab[l-1]-tab[l]);
cnt=tab[l]+x;
if(tab[l-1]<cnt) sum-=1ll*s*(tab[l-1]-cnt);
else sum-=1ll*t*(tab[l-1]-cnt);
if(r<n){
cnt=tab[r]+x;
if(tab[r]<tab[r+1]) sum+=1ll*s*(tab[r]-tab[r+1]);
else sum+=1ll*t*(tab[r]-tab[r+1]);
if(cnt<tab[r+1]) sum-=1ll*s*(cnt-tab[r+1]);
else sum-=1ll*t*(cnt-tab[r+1]);
}*/
}
}
Compilation message (stderr)
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:77:47: warning: 'righty' may be used uninitialized in this function [-Wmaybe-uninitialized]
77 | if(right<righty) sum-=1ll*s*(right-righty);
| ~~~~~~^~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |