제출 #1199428

#제출 시각아이디문제언어결과실행 시간메모리
1199428Saul0906Foehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
272 ms24692 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define rep(a,b,c) for(int a=b; a<c; a++) #define repr(a,b,c) for(int a=b-1; a>c-1; a--) #define repa(a,b) for(auto a:b) #define mid ((l+r)>>1) #define endl "\n" using namespace std; const int N=2e5+5; ll a[N]; struct segtree{ segtree *left, *right; int l, r; ll v; segtree(int x, int y): l(x), r(y){ v=a[l]; if(l==r) return; v=0; left = new segtree(l,mid); right = new segtree(mid+1,r); } void update(int x, int y, ll z){ if(y<l || r<x) return; if(x<=l && r<=y){ v+=z; return; } left->update(x,y,z); right->update(x,y,z); } ll query(int x){ if(x<l || r<x) return 0; if(x<=l && r<=x) return v; return left->query(x)+right->query(x)+v; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n, q, s, t, ans=0; cin>>n>>q>>s>>t; s*=-1; rep(i,0,n+1) cin>>a[i]; rep(i,1,n+1){ if(a[i]>a[i-1]) ans+=s*(a[i]-a[i-1]); else ans+=t*(a[i-1]-a[i]); } ll l, r, x; segtree st(0,n); while(q--){ cin>>l>>r>>x; ll a, b, c, d; a=st.query(l-1); b=st.query(l); c=st.query(r); d=st.query(r+1); st.update(l,r,x); if(b>a) ans-=s*(b-a); else ans-=t*(a-b); b+=x; if(b>a) ans+=s*(b-a); else ans+=t*(a-b); if(r<n){ if(d>c) ans-=s*(d-c); else ans-=t*(c-d); c+=x; if(d>c) ans+=s*(d-c); else ans+=t*(c-d); } cout<<ans<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...