제출 #751260

#제출 시각아이디문제언어결과실행 시간메모리
751260aufanFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
133 ms7284 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define all(x) (x).begin(), (x).end() using namespace std; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q, s, t; cin >> n >> q >> s >> t; vector<int> zx(n+5); for (int i = 0; i <= n; i++) cin >> zx[i]; vector<int> fen(n+5, 0); auto add = [&](int x, int val) { for (;x<=n;x+=x&-x) fen[x] += val; }; auto get = [&](int x) { int res = 0; for (;x>0;x-=x&-x) res += fen[x]; return res; }; for (int i = 1; i <= n; i++) { add(i, zx[i]); add(i+1, -zx[i]); } int ans = 0; for (int i = 0; i < n; i++) { if (zx[i] < zx[i+1]) { ans -= s*(zx[i+1] - zx[i]); } else { ans += t*(zx[i] - zx[i+1]); } } while (q --> 0) { int l, r, x; cin >> l >> r >> x; zx[l-1] = get(l-1); zx[l] = get(l); if (zx[l-1] < zx[l]) { ans += s*(zx[l] - zx[l-1]); } else { ans -= t*(zx[l-1] - zx[l]); } if (r < n) { zx[r] = get(r); zx[r+1] = get(r+1); if (zx[r] < zx[r+1]) { ans += s*(zx[r+1] - zx[r]); } else { ans -= t*(zx[r] - zx[r+1]); } } add(l, x); add(r+1, -x); zx[l] += x; if (zx[l-1] < zx[l]) { ans -= s*(zx[l] - zx[l-1]); } else { ans += t*(zx[l-1] - zx[l]); } if (r < n) { if (l != r) zx[r] += x; if (zx[r] < zx[r+1]) { ans -= s*(zx[r+1] - zx[r]); } else { ans += t*(zx[r] - zx[r+1]); } } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...