제출 #354865

#제출 시각아이디문제언어결과실행 시간메모리
354865SeDunionFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
276 ms13292 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e6 + 66; ll f[N]; void upd(int pos, ll v) { while (pos < N) { f[pos] += v; pos |= pos + 1; } } ll gt(int pos) { ll r = 0; while (pos >= 0) { r += f[pos]; pos &= pos + 1; pos--; } return r; } ll a[N], S, T, All; int n, q; ll get(int i) { if (i >= n || i < 0) return 0; if (a[i] + gt(i) < a[i + 1] + gt(i + 1)) { return (a[i] + gt(i) - a[i + 1] - gt(i + 1)) * S; } else { return (a[i] + gt(i) - a[i + 1] - gt(i + 1)) * T; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> q >> S >> T; for (int i = 0 ; i <= n ; ++ i) { cin >> a[i]; } for (int i = 0 ; i < n ; ++ i) { All += get(i); } while (q--) { int l, r; ll x; cin >> l >> r >> x; All -= get(l-1); All -= get(r); upd(l, x); upd(r+1,-x); All += get(l-1); All += get(r); cout << All << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...