제출 #901420

#제출 시각아이디문제언어결과실행 시간메모리
901420BlagojFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
476 ms24068 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define all(x) (x).begin(), (x).end() const int mxn = 2e5 + 10; ll a[mxn]; struct SegmentTree { vector<ll> sgt, lz; SegmentTree(int sz) { sgt.resize(4 * sz); lz.resize(4 * sz); } void build(int k, int l, int r) { if (l == r) { sgt[k] = a[l]; return; } int m = (l + r) / 2; build(k * 2, l, m); build(k * 2 + 1, m + 1, r); } void push(int k, int l, int r) { if (lz[k]) { sgt[k] += lz[k]; if (l != r) { lz[k * 2] += lz[k]; lz[k * 2 + 1] += lz[k]; } lz[k] = 0; } } void update(int k, int l, int r, int i, int j, ll val) { push(k, l, r); if (l > j || r < i) return; if (i <= l && r <= j) { lz[k] += val; push(k, l, r); return; } int m = (l + r) / 2; update(k * 2, l, m, i, j, val); update(k * 2 + 1, m + 1, r, i, j, val); } ll get(int k, int l, int r, int i) { push(k, l, r); if (l == r) return sgt[k]; int m = (l + r) / 2; if (m >= i) return get(k * 2, l, m, i); return get(k * 2 + 1, m + 1, r, i); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q, s, t; cin >> n >> q >> s >> t; n++; for (int i = 0; i < n; i++) cin >> a[i]; SegmentTree sgt(n); sgt.build(1, 0, n - 1); ll ans = 0; for (int i = 1; i < n; i++) { if (a[i - 1] < a[i]) ans += (a[i] - a[i - 1]) * s; else ans += (a[i] - a[i - 1]) * t; } while (q--) { int l, r, x; cin >> l >> r >> x; a[l - 1] = sgt.get(1, 0, n - 1, l - 1); a[l] = sgt.get(1, 0, n - 1, l); if (a[l - 1] < a[l]) ans -= (a[l] - a[l - 1]) * s; else ans -= (a[l] - a[l - 1]) * t; if (l < n - 1) { a[l + 1] = sgt.get(1, 0, n - 1, l + 1); if (a[l] < a[l + 1]) ans -= (a[l + 1] - a[l]) * s; else ans -= (a[l + 1] - a[l]) * t; } if (l != r) { if (l + 1 < r) { a[r - 1] = sgt.get(1, 0, n - 1, r - 1); a[r] = sgt.get(1, 0, n - 1, r); if (a[r - 1] < a[r]) ans -= (a[r] - a[r - 1]) * s; else ans -= (a[r] - a[r - 1]) * t; } if (r < n - 1) { a[r + 1] = sgt.get(1, 0, n - 1, r + 1); if (a[r] < a[r + 1]) ans -= (a[r + 1] - a[r]) * s; else ans -= (a[r + 1] - a[r]) * t; } } sgt.update(1, 0, n - 1, l, r, x); a[l - 1] = sgt.get(1, 0, n - 1, l - 1); a[l] = sgt.get(1, 0, n - 1, l); if (a[l - 1] < a[l]) ans += (a[l] - a[l - 1]) * s; else ans += (a[l] - a[l - 1]) * t; if (l < n - 1) { a[l + 1] = sgt.get(1, 0, n - 1, l + 1); if (a[l] < a[l + 1]) ans += (a[l + 1] - a[l]) * s; else ans += (a[l + 1] - a[l]) * t; } if (l != r) { if (l + 1 < r) { a[r - 1] = sgt.get(1, 0, n - 1, r - 1); a[r] = sgt.get(1, 0, n - 1, r); if (a[r - 1] < a[r]) ans += (a[r] - a[r - 1]) * s; else ans += (a[r] - a[r - 1]) * t; } if (r < n - 1) { a[r + 1] = sgt.get(1, 0, n - 1, r + 1); if (a[r] < a[r + 1]) ans += (a[r + 1] - a[r]) * s; else ans += (a[r + 1] - a[r]) * t; } } cout << -ans << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...