제출 #1020155

#제출 시각아이디문제언어결과실행 시간메모리
1020155DucNguyen2007Foehn Phenomena (JOI17_foehn_phenomena)C++14
0 / 100
291 ms27496 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pll pair<ll,ll> #define fi first #define se second const ll inf=2e18; const int maxN=3e5+5; int n,q; ll a[maxN+1],s,t,ans=0; struct segment { struct Node { ll s,lazy; Node() { s=lazy=0; } Node(ll S,ll laz) { s=S; lazy=laz; } }sum[4*maxN+1]; Node meg(Node x,Node y) { Node res; res.s=x.s+y.s; res.lazy=0; return res; } void lazyupdate(int x,int low,int high) { if(low==high) { return; } int mid=(low+high)/2; sum[2*x].s+=(sum[x].lazy*(mid-low+1)); sum[2*x].lazy+=sum[x].lazy; sum[2*x+1].s+=(sum[x].lazy*(high-mid)); sum[2*x+1].lazy+=sum[x].lazy; sum[x].lazy=0; } void Build(int x,int low,int high) { if(low==high) { sum[x]=Node(a[low],0); return; } int mid=(low+high)/2; Build(2*x,low,mid); Build(2*x+1,mid+1,high); sum[x]=meg(sum[2*x],sum[2*x+1]); } int l,r,val; void Update(int x,int low,int high) { if(low>r||high<l) { return; } if(low>=l&&high<=r) { sum[x].s+=(1LL*val*(high-low+1)); sum[x].lazy+=val; return; } lazyupdate(x,low,high); int mid=(low+high)/2; Update(2*x,low,mid); Update(2*x+1,mid+1,high); sum[x]=meg(sum[2*x],sum[2*x+1]); } void update_val(int l,int r,int val) { this->l=l; this->r=r; this->val=val; Update(1,0,n); } Node get(int x,int low,int high) { if(low>r||high<l) { return Node(0,0); } if(low>=l&&high<=r) { return sum[x]; } lazyupdate(x,low,high); int mid=(low+high)/2; Node get1=get(2*x,low,mid); Node get2=get(2*x+1,mid+1,high); return meg(get1,get2); } Node query(int l,int r) { this->l=l; this->r=r; return get(1,0,n); } }st; void solve1(ll base,ll tmp,ll pos) { if(base>a[pos-1]) { ans+=((base-a[pos-1])*s); if(tmp<=a[pos-1]) { ans+=((a[pos-1]-tmp)*t); } else ans-=((tmp-a[pos-1])*s); } else { ans-=((a[pos-1]-base)*t); if(tmp<=a[pos-1]) { ans+=((a[pos-1]-tmp)*t); } else ans-=((tmp-a[pos-1])*s); } } void solve2(ll base,ll tmp,ll pos) { if(base>=a[pos]) { ans-=((base-a[pos])*t); if(tmp<a[pos]) { ans-=((a[pos]-tmp)*s); } else ans+=((tmp-a[pos])*t); } else { ans+=((a[pos]-base)*s); if(tmp>=a[pos]) { ans+=((tmp-a[pos])*t); } else ans-=((a[pos]-tmp)*s); } } int main() { //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q>>s>>t; for(int i=0;i<=n;i++) { cin>>a[i]; } st.Build(1,0,n); for(int i=1;i<=n;i++) { if(a[i-1]<a[i]) { ans-=((a[i]-a[i-1])*s); } else ans+=((a[i-1]-a[i])*t); } cout<<ans<<'\n'; while(q--) { int l,r; ll x; cin>>l>>r>>x; ll base1=st.query(l,l).s,base2=st.query(r,r).s; st.update_val(l,r,x); ll tmp1=st.query(l,l).s,tmp2=st.query(r,r).s; solve1(base1,tmp1,l); if(r+1<=n) { solve2(base2,tmp2,r+1); } cout<<ans<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...