제출 #900190

#제출 시각아이디문제언어결과실행 시간메모리
900190aykhnFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
233 ms16468 KiB
#include <bits/stdc++.h> // author: aykhn using namespace std; typedef long long ll; #define all(v) v.begin(), v.end() #define pii pair<int, int> #define mpr make_pair #define eb emplace_back #define pb push_back #define ts to_string #define fi first #define se second #define ins insert #define int ll #define inf 0x3F3F3F3F #define infll 0x3F3F3F3F3F3F3F3FLL #define bpc __builtin_popcount const int MXN = 2e5 + 5; int n, sz = 1; int q, s, t; int st[4 * MXN], a[MXN]; void build(int l, int r, int x) { if (l + 1 == r) { st[x] = a[l]; return; } int mid = (l + r) >> 1; build(l, mid, 2*x + 1), build(mid, r, 2*x + 2); } void add(int l, int r, int x, int lx, int rx, int val) { if (l >= rx || r <= lx) return; if (l >= lx && r <= rx) { st[x] += val; return; } int mid = (l + r) >> 1; add(l, mid, 2*x + 1, lx, rx, val), add(mid, r, 2*x + 2, lx, rx, val); } int get(int l, int r, int x, int ind) { if (l + 1 == r) return st[x]; int mid = (l + r) >> 1; if (ind < mid) return st[x] + get(l, mid, 2*x + 1, ind); else return st[x] + get(mid, r, 2*x + 2, ind); } signed main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); int n, q, s, t; cin >> n >> q >> s >> t; n++; while (sz < n) sz <<= 1; int res = 0; for (int i = 0; i < n; i++) { cin >> a[i]; if (!i) continue; if (a[i - 1] < a[i]) res += (a[i - 1] - a[i]) * s; else res += (a[i - 1] - a[i]) * t; } build(0, sz, 0); while (q--) { int l, r, val; cin >> l >> r >> val; int a = get(0, sz, 0, l - 1), b = get(0, sz, 0, l), c = get(0, sz, 0, r), d = get(0, sz, 0, r + 1); if (a < b) res -= (a - b) * s; else res -= (a - b) * t; if (r + 1 < n && c < d) res -= (c - d) * s; else if (r + 1 < n) res -= (c - d) * t; add(0, sz, 0, l, r + 1, val); b = get(0, sz, 0, l), c = get(0, sz, 0, r); if (a < b) res += (a - b) * s; else res += (a - b) * t; if (r + 1 < n && c < d) res += (c - d) * s; else if (r + 1 < n) res += (c - d) * t; cout << res << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...