제출 #670508

#제출 시각아이디문제언어결과실행 시간메모리
670508S2speedFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
126 ms13132 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn = 2e5 + 17; struct fentree { ll sz; vector<ll> val; void init(ll n){ sz = n; val.assign(sz , 0); return; } void add(ll i , ll k){ ll h = i; while(h < sz){ val[h] += k; h |= (h + 1); } return; } ll cal(ll i){ ll h = i , res = 0; while(~h){ res += val[h]; h &= (h + 1); h--; } return res; } }; ll n , q , s , t; fentree ft; ll a[maxn]; ll dif(ll a , ll b){ return (b > a ? s : t) * (a - b); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>q>>s>>t; for(ll i = 0 ; i <= n ; i++){ cin>>a[i]; } ft.init(n + 1); for(ll i = 1 ; i <= n ; i++){ ft.add(i , a[i] - a[i - 1]); } ll res = 0; for(ll i = 1 ; i <= n ; i++){ res += dif(a[i - 1] , a[i]); } for(ll e = 0 ; e < q ; e++){ ll l , r , k; cin>>l>>r>>k; ll hl = ft.cal(l - 1) , hr = ft.cal(l); ll pr = dif(hl , hr) , cur = dif(hl , hr + k); res += cur - pr; if(r < n){ hl = ft.cal(r); hr = ft.cal(r + 1); pr = dif(hl , hr); cur = dif(hl + k , hr); res += cur - pr; } ft.add(l , k); ft.add(r + 1 , -k); cout<<res<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...