Submission #545767

#TimeUsernameProblemLanguageResultExecution timeMemory
545767JomnoiFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
398 ms26356 KiB
#include <bits/stdc++.h> #define DEBUG 0 using namespace std; const int N = 2e5 + 10; long long S, T; class A { public : long long leftmost, rightmost, windtemp; A() {} A(const long long &l, const long long &r, const long long &w) : leftmost(l), rightmost(r), windtemp(w) {} A operator+(const A &o) const { long long l, r, w; l = leftmost; r = o.rightmost; w = windtemp + o.windtemp; if(rightmost < o.leftmost) { w -= S * (o.leftmost - rightmost); } else { w += T * (rightmost - o.leftmost); } return A(l, r, w); } }; class SegmentTree { private : A tree[4 * N]; long long lazy[4 * N]; public : void build(const int &idx, const int &l, const int &r) { if(l == r) { int a; cin >> a; tree[idx] = A(a, a, 0); return; } int mid = (l + r) / 2; build(idx * 2, l, mid); build(idx * 2 + 1, mid + 1, r); tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]; } void push(const int &idx, const int &l, const int &r) { if(lazy[idx] == 0) { return; } tree[idx].leftmost += lazy[idx]; tree[idx].rightmost += lazy[idx]; if(l != r) { lazy[idx * 2] += lazy[idx]; lazy[idx * 2 + 1] += lazy[idx]; } lazy[idx] = 0; } void update(const int &idx, const int &l, const int &r, const int &ql, const int &qr, const int &x) { push(idx, l, r); if(r < ql or qr < l) { return; } if(ql <= l and r <= qr) { lazy[idx] += x; push(idx, l, r); return; } int mid = (l + r) / 2; update(idx * 2, l, mid, ql, qr, x); update(idx * 2 + 1, mid + 1, r, ql, qr, x); tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]; } long long get_ans() { return tree[1].windtemp; } }ST; int main() { cin.tie(0)->sync_with_stdio(0); int n, q; cin >> n >> q >> S >> T; ST.build(1, 0, n); while(q--) { int l, r, x; cin >> l >> r >> x; ST.update(1, 0, n, l, r, x); cout << ST.get_ans() << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...