Submission #1159700

#TimeUsernameProblemLanguageResultExecution timeMemory
1159700brover29Foehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
519 ms13988 KiB
#include <bits/stdc++.h> //qwerty47924692 using namespace std; using ll = long long; const ll N=2e5+29; const string br="617283"; #define sz(a)(ll)a.size() #define f first #define s second ll n,a[N],q,t,s,ans,z[4*N],st[4*N]; void push(ll v,ll l,ll r){ if(!z[v])return; ll mid=(r+l)/2; st[v*2]+=z[v]*(mid-l+1); st[v*2+1]+=z[v]*(r-mid); z[v*2]+=z[v]; z[v*2+1]+=z[v]; z[v]=0; return; } void build(ll v,ll l,ll r){ if(l==r){ st[v]=a[l]; return; } ll mid=(r+l)/2; build(v*2,l,mid); build(v*2+1,mid+1,r); st[v]=st[v*2]+st[v*2+1]; } void upd(ll v,ll l,ll r,ll x,ll y,ll value){ if(l>y||x>r)return; if(x<=l&&r<=y){ st[v]+=value*(r-l+1); z[v]+=value; return; } push(v,l,r); ll mid=(r+l)/2; upd(v*2,l,mid,x,y,value); upd(v*2+1,mid+1,r,x,y,value); st[v]=st[v*2]+st[v*2+1]; return; } ll get(ll v,ll l,ll r,ll x,ll y){ if(l>y||x>r) { return 0; } if(x<=l&&r<=y){ return st[v]; } push(v,l,r); ll mid=(r+l)/2; return get(v*2,l,mid,x,y)+get(v*2+1,mid+1,r,x,y); } void upd(ll i,ll x){ a[i]=get(1,1,n-1,i,i); a[i-1]=get(1,1,n-1,i-1,i-1); a[i+1]=get(1,1,n-1,i+1,i+1); if(a[i-1]<a[i])ans+=x*abs(a[i]-a[i-1])*(-s); if(a[i-1]>a[i])ans+=x*abs(a[i]-a[i-1])*t; if(a[i]<a[i+1]&&i+1<n)ans+=x*abs(a[i+1]-a[i])*(-s); if(a[i]>a[i+1]&&i+1<n)ans+=x*abs(a[i+1]-a[i])*t; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>q>>s>>t; n++; for(ll i=0;i<n;i++){ cin>>a[i]; } build(1,1,n-1); for(ll i=1;i<n;i+=2)upd(i,1); while(q--){ ll l,r,x; cin>>l>>r>>x; upd(l,-1); if(r!=l)upd(r,-1); // for(ll i=1;i<n;i++)cout<<get(1,1,n-1,i,i)<<' '; upd(1,1,n-1,l,r,x); upd(l,1); if(r!=l)upd(r,1); cout<<ans<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...