제출 #585421

#제출 시각아이디문제언어결과실행 시간메모리
585421jairRSFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
794 ms19796 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define all(s) s.begin(), s.end() typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; ll n, q, s, t; ll getTempDiff(ll heightLeft, ll heightRight) { ll heightDif = abs(heightLeft - heightRight), res = 0; if (heightLeft < heightRight) res -= s * heightDif; else res += t * heightDif; return res; } struct node { ll value; node(ll _value = 0) : value(_value) {} }; struct segmentTree { int size, power2 = 1; node nullNode = node(); vector<node> tree; vector<ll> lazy; segmentTree(int n, node _nullNode) { nullNode = _nullNode; while (power2 < n) power2 *= 2; size = 2 * power2 - 1; tree = vector<node>(size + 1, _nullNode); lazy = vector<ll>(size + 1, 0); } virtual node merge(node &a, node &b) = 0; void update(int i, node v) { int in = i + size / 2; tree[in] = v; in /= 2; while (in > 0) { tree[in] = merge(tree[in * 2], tree[in * 2 + 1]); in /= 2; } } void update(int l, int r, int queryL, int queryR, int v, int i = 1) { pushLazy(i, l, r); if (l > queryR || r < queryL) return; if (queryL <= l && r <= queryR) { lazy[i] = v; return; } int mid = (l + r) / 2; update(l, mid, queryL, queryR, v, i * 2); update(mid + 1, r, queryL, queryR, v, i * 2 + 1); } virtual void pushLazy(int i, int l, int r) = 0; node query(int l, int r, int queryL, int queryR, int i = 1) { pushLazy(i, l, r); if (l > queryR || r < queryL) return nullNode; if (queryL <= l && r <= queryR) return tree[i]; int mid = (l + r) / 2; node query1 = query(l, mid, queryL, queryR, i * 2); node query2 = query(mid + 1, r, queryL, queryR, i * 2 + 1); return merge(query1, query2); } }; struct sumSegmentTree : segmentTree { sumSegmentTree(int n, node _nullNode) : segmentTree(n, _nullNode) {} node merge(node &a, node &b) { return a.value + b.value; } void pushLazy(int i, int l, int r) { tree[i].value += lazy[i] * (ll)(r - l + 1); if (i * 2 <= size) { lazy[i * 2] += lazy[i]; lazy[i * 2 + 1] += lazy[i]; } lazy[i] = 0; } ll get(int i) { return query(1, power2, i, i).value; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q >> s >> t; vector<ll> height(n + 1, 0); for (int i = 0; i <= n; i++) cin >> height[i]; sumSegmentTree segTree(n, node()); for (int i = 1; i <= n; i++) segTree.update(i, height[i]); ll temp = 0; for (int i = 0; i < n; i++) temp += getTempDiff(height[i], height[i + 1]); while (q--) { ll l, r, k; cin >> l >> r >> k; temp -= getTempDiff(segTree.get(l - 1), segTree.get(l)); if (r < n) temp -= getTempDiff(segTree.get(r), segTree.get(r + 1)); segTree.update(1, segTree.power2, l, r, k); temp += getTempDiff(segTree.get(l - 1), segTree.get(l)); if (r < n) temp += getTempDiff(segTree.get(r), segTree.get(r + 1)); cout << temp << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...