Submission #1166515

#TimeUsernameProblemLanguageResultExecution timeMemory
1166515chikien2009Foehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
296 ms29964 KiB
#include <bits/stdc++.h> using namespace std; inline void setup() { // #ifndef ONLINE_JUDGE // freopen("test.inp", "r", stdin); // freopen("test.out", "w", stdout); // #endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int n, q, s, t, a[200001], b, c, e, f; class SEGMENT_TREE { private: long long first_altitude; vector<long long> pre, suf, val, rem; inline void ProcessNode(int ind) { long long d; pre[ind] = pre[ind << 1]; suf[ind] = suf[ind << 1 | 1]; d = suf[ind << 1] - pre[ind << 1 | 1]; d *= (d < 0 ? s : t); val[ind] = val[ind << 1] + val[ind << 1 | 1] + d; } inline void UpdateNode(int ind, int l, int r) { if (l != r) { rem[ind << 1] += rem[ind]; rem[ind << 1 | 1] += rem[ind]; } pre[ind] += rem[ind]; suf[ind] += rem[ind]; rem[ind] = 0; } inline void Build(int ind, int l, int r) { if (l == r) { val[ind] = rem[ind] = 0; pre[ind] = suf[ind] = a[l]; return; } int m = (l + r) >> 1, d; Build(ind << 1, l, m); Build(ind << 1 | 1, m + 1, r); ProcessNode(ind); } inline void Update(int ind, int l, int r, int x, int y, int v) { UpdateNode(ind, l, r); if (r < x || y < l) { return; } if (x <= l && r <= y) { rem[ind] += v; UpdateNode(ind, l, r); return; } int m = (l + r) >> 1; Update(ind << 1, l, m, x, y, v); Update(ind << 1 | 1, m + 1, r, x, y, v); ProcessNode(ind); } public: inline void Init() { first_altitude = a[1]; pre.resize(n << 2); suf.resize(n << 2); val.resize(n << 2); rem.resize(n << 2); Build(1, 1, n); } inline void Update(int x, int y, int v) { Update(1, 1, n, x, y, v); first_altitude += (x == 1) * v; } inline long long Get() { if (first_altitude > 0) { return -first_altitude * s + val[1]; } return -first_altitude * t + val[1]; } } st; int main() { setup(); cin >> n >> q >> s >> t; for (int i = 0; i <= n; ++i) { cin >> a[i]; } st.Init(); while (q--) { cin >> b >> c >> e; st.Update(b, c, e); cout << st.Get() << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...