제출 #33555

#제출 시각아이디문제언어결과실행 시간메모리
33555ubiratan37Foehn Phenomena (JOI17_foehn_phenomena)C++98
30 / 100
306 ms6772 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int bit[2][212345]; void init(int n){ for(int i=1; i<=n; i++){ bit[0][i] = 0; bit[1][i] = 0; } } //auxiliar void update(int *bit, int idx, int val, int n){ for(int i = idx; i <= n; i += i&-i){ bit[i]+=val; } } //auxiliar int query(int *bit, int idx){ int ans = 0; for(int i=idx; i>0; i -= i&-i){ ans += bit[i]; } return ans; } void range_update(int l, int r, int val, int n){ update(bit[0], l, val, n); update(bit[0], r+1, -val, n); update(bit[1], l, val*(l-1), n); update(bit[1], r+1, -val*r, n); } int prefix_query(int idx){ return query(bit[0],idx)*idx - query(bit[1], idx); } int range_query(int l, int r){ return prefix_query(r) - prefix_query(l-1); } int32_t main(){ int n,q,s,t; cin >> n >> q >> s >> t; n++; init(n); int v[n]; for(int i=1; i<=n; i++){ cin >> v[i]; range_update(i,i,v[i],n); } int ans = 0; for(int i=1; i<n; i++){ if(v[i] < v[i+1]) ans -= abs(v[i+1]-v[i])*s; else ans += abs(v[i+1]-v[i])*t; } while(q--){ int l,r,x; cin >> l >> r >> x; l++, r++; if(l > 1){ v[l-1] = range_query(l-1, l-1); v[l] = range_query(l,l); if(v[l-1] < v[l]) ans += abs(v[l] - v[l-1])*s; else ans -= abs(v[l] - v[l-1])*t; if(v[l-1] < v[l]+x) ans -= abs(v[l]+x - v[l-1])*s; else ans += abs(v[l]+x - v[l-1])*t; } if(r < n){ v[r] = range_query(r, r); v[r+1] = range_query(r+1,r+1); if(v[r] < v[r+1]) ans += abs(v[r] - v[r+1])*s; else ans -= abs(v[r] - v[r+1])*t; if(v[r]+x < v[r+1]) ans -= abs(v[r]+x - v[r+1])*s; else ans += abs(v[r]+x - v[r+1])*t; } range_update(l,r,x,n); cout << ans << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...