제출 #926542

#제출 시각아이디문제언어결과실행 시간메모리
926542SuPythonyFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
517 ms17744 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAX=2*1e5+7; vector<ll> bit1(MAX,0); vector<ll> bit2(MAX,0); vector<ll> incr(MAX,0); vector<ll> decr(MAX,0); ll n; void upd1(int pos, ll val) { while (pos<=n) { bit1[pos]+=val; pos+=pos&-pos; } } void upd2(int pos, ll val) { while (pos<=n) { bit2[pos]+=val; pos+=pos&-pos; } } ll query1(int pos) { ll ans=0; while (pos>0) { ans+=bit1[pos]; pos-=pos&-pos; } return ans; } ll query2(int pos) { ll ans=0; while (pos>0) { ans+=bit2[pos]; pos-=pos&-pos; } return ans; } int main() { ll q,s,t; cin>>n>>q>>s>>t; vector<ll> a(n+1); for (int i=0; i<=n; i++) cin>>a[i]; for (int i=1; i<=n; i++) { if (a[i]>a[i-1]) { incr[i]=a[i]-a[i-1]; upd1(i,incr[i]); } else { decr[i]=a[i-1]-a[i]; upd2(i,decr[i]); } } while (q--) { ll l,r,x; cin>>l>>r>>x; if (incr[l]!=0) { if (incr[l]+x>=0) { upd1(l,x); incr[l]+=x; } else { upd2(l,-x-incr[l]); decr[l]+=-x-incr[l]; upd1(l,-incr[l]); incr[l]+=-incr[l]; } } else { x=-x; if (decr[l]+x>=0) { upd2(l,x); decr[l]+=x; } else { upd1(l,-x-decr[l]); incr[l]+=-x-decr[l]; upd2(l,-decr[l]); decr[l]+=-decr[l]; } x=-x; } if (r<n) { x=-x; l=r+1; if (incr[l]!=0) { if (incr[l]+x>=0) { upd1(l,x); incr[l]+=x; } else { upd2(l,-x-incr[l]); decr[l]+=-x-incr[l]; upd1(l,-incr[l]); incr[l]+=-incr[l]; } } else { x=-x; if (decr[l]+x>=0) { upd2(l,x); decr[l]+=x; } else { upd1(l,-x-decr[l]); incr[l]+=-x-decr[l]; upd2(l,-decr[l]); decr[l]+=-decr[l]; } x=-x; } } cout<<t*query2(n)-s*query1(n)<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...