Submission #594975

#	Time	Username	Problem	Language	Result	Execution time	Memory
594975		piOOE	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	192 ms	13124 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template<typename T>
struct Fenwick {
    vector<T> t;
    int sz;

    Fenwick() = default;
    Fenwick(int n) {
        init(n);
    }

    void init(int n) {
        t.assign(n, 0);
        sz = n;
    }

    void modify(int i, T v) {
        for (; i < sz; i |= (i + 1)) {
            t[i] += v;
        }
    }

    T get(int i) {
        T ans = 0;
        for (; i > -1; i = ((i + 1) & i) - 1) {
            ans += t[i];
        }
        return ans;
    }

    //[l, r)
    T get(int l, int r) {
        return get(r - 1) - get(l - 1);
    }
    //[l, r)
    void modify(int l, int r, T v) {
        modify(l, v);
        modify(r, -v);
    }

};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    vector<ll> a(n + 1);
    Fenwick<ll> fn(n + 1);
    for (int i = 0; i <= n; ++i) {
        cin >> a[i];
        fn.modify(i, i + 1, a[i]);
    }
    auto upd = [&](int i) {
        if (i > n) return 0ll;
        a[i] = fn.get(i), a[i - 1] = fn.get(i - 1);
        return (a[i] > a[i - 1] ? -s : t) * (ll)abs(a[i] - a[i - 1]);
    };
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += upd(i);
    }
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        ans -= upd(l);
        ans -= upd(r + 1);
        fn.modify(l, r + 1, x);
        ans += upd(l);
        ans += upd(r + 1);
        cout << ans << '\n';
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60