제출 #860687

#제출 시각아이디문제언어결과실행 시간메모리
860687Iliya_Foehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
220 ms17744 KiB
//IN THE NAME OF GOD #include<bits/stdc++.h> #pragma GCC optimize("O2,unroll-loops") #define endl '\n' #define F first #define S second using namespace std; typedef long long ll; const ll N = 2e5+7; ll a[N], seg[N<<2]; void build(ll ind, ll l, ll r){ if (l == r){ seg[ind] = a[l]; return; } ll mid = (l+r)>>1; build(2*ind,l,mid); build(2*ind+1,mid+1,r); } void shift(ll ind, ll l, ll r){ if (l == r) return; seg[2*ind] += seg[ind]; seg[2*ind+1] += seg[ind]; seg[ind] = 0; } void upd(ll ind, ll l, ll r, ll st, ll en, ll val){ shift(ind,l,r); if (l > en || st > r) return; if (l == r || (l >= st && r <= en)){ seg[ind] += val; return; } ll mid = (l+r)>>1; upd(2*ind,l,mid,st,en,val); upd(2*ind+1,mid+1,r,st,en,val); } ll get(ll ind, ll l, ll r, ll id){ shift(ind,l,r); if (l == r) return seg[ind]; ll mid = (l+r)>>1; if (id <= mid) return get(2*ind,l,mid,id); else return get(2*ind+1,mid+1,r,id); } int32_t main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n,q,s,t; cin >> n >> q >> s >> t; for(ll i=0; i<=n; i++) cin >> a[i]; build(1,0,n); ll mos = 0, man = 0; for(ll i=1; i<=n; i++){ if (a[i] > a[i-1]) man += (a[i] - a[i-1]); else mos += (a[i-1] - a[i]); } while(q--){ ll l,r,x; cin >> l >> r >> x; if (l > 0){ ll a = get(1,0,n,l-1), b = get(1,0,n,l); if (a < b) man -= (b-a); else mos -= (a-b); b += x; if (a < b) man += (b-a); else mos += (a-b); } if (r < n){ ll a = get(1,0,n,r), b = get(1,0,n,r+1); if (a < b) man -= (b-a); else mos -= (a-b); a += x; if (a < b) man += (b-a); else mos += (a-b); } upd(1,0,n,l,r,x); ll ans = mos * t - man * s; cout << ans << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...