Submission #1199463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199463		efishel	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	86 ms	7348 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

struct Fenwick {
    vll tree;
    ll n;

    Fenwick (ll n): tree(n, 0), n(n) {}

    void update (ll l, ll r, ll val) { update(l, val); update(r+1, -val); }
    void update (ll id, ll val) {
        for (; id < n; id |= id+1) tree[id] += val;
    }

    ll query (ll id) {
        ll ans = 0;
        for (; id >= 0; id &= id+1, id--) ans += tree[id];
        return ans;
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, Q, vP, vM;
    cin >> n >> Q >> vP >> vM;
    vll ve(n+1);
    for (ll &i : ve) cin >> i;
    Fenwick ft(n+1);
    for (ll i = 0; i < n+1; i++) {
        ft.update(i, i, ve[i]);
    }
    ll ans = 0;
    for (ll i = 1; i < n+1; i++) {
        ll diff = ve[i] - ve[i-1];
        if (diff > 0)
            ans -= vP*diff;
        else
            ans -= vM*diff;
    }
    const auto fgetDiff = [&](ll i) -> ll {
        assert(i > 0);
        if (i >= n+1) return 0;
        return ft.query(i) - ft.query(i-1);
    };
    const auto fadjDelta = [&](ll i, ll mult) {
        ll diff = fgetDiff(i);
        if (diff > 0)
            ans -= vP*diff*mult;
        else
            ans -= vM*diff*mult;
    };
    while (Q--) {
        ll ql, qr, val;
        cin >> ql >> qr >> val;
        fadjDelta(ql  , -1);
        fadjDelta(qr+1, -1);
        ft.update(ql, qr, val);
        fadjDelta(ql  , +1);
        fadjDelta(qr+1, +1);
        cout << ans << '\n';
    }
    return 0;
}

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