Submission #856370

#TimeUsernameProblemLanguageResultExecution timeMemory
856370Namviet2704Foehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
221 ms26972 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 5; int n, q, s, t; ll a[N]; struct st { ll left, right, val; ll lazy; } nodes[N * 4]; void down(int id) { ll t = nodes[id].lazy; nodes[id * 2].lazy += t; nodes[id * 2].left += t; nodes[id * 2].right += t; nodes[id * 2 + 1].lazy += t; nodes[id * 2 + 1].left += t; nodes[id * 2 + 1].right += t; nodes[id].lazy = 0; } st merge(st A, st B) { if (A.right < B.left) A.val += B.val - (B.left - A.right) * s; else A.val += B.val + (A.right - B.left) * t; A.right = B.right; return A; } void build(int id, int l, int r) { if (l == r) { nodes[id].left = nodes[id].right = a[l]; return; } int mid = (l + r) >> 1; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); nodes[id] = merge(nodes[id * 2], nodes[id * 2 + 1]); } void update(int id, int l, int r, int u, int v, ll val) { // cout << nodes[3].lazy << '\n'; if (v < l || r < u) return; if (u <= l && r <= v) { nodes[id].left += val; nodes[id].right += val; // cout << id << " " << l << " " << r << " " << nodes[id].lazy << "haha" << '\n'; nodes[id].lazy += val; return; } int mid = (l + r) / 2; down(id); update(id * 2, l, mid, u, v, val); update(id * 2 + 1, mid + 1, r, u, v, val); ll h = nodes[id].lazy; nodes[id] = merge(nodes[id * 2], nodes[id * 2 + 1]); nodes[id].lazy = h; } int main() { // freopen(task".inp", "r", stdin); // freopen(task".out", "w", stdout); 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]; build(1, 0, n); // cout << nodes[3].lazy << '\n'; for (int i = 1; i <= q; i++) { int x, y; ll val; cin >> x >> y >> val; update(1, 0, n, x, y, val); cout << nodes[1].val << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...