Submission #635888

#	Time	Username	Problem	Language	Result	Execution time	Memory
635888		ljuba	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	167 ms	13140 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

class FenwickTree {
private:
    int n;
    vector<ll> ft;
public:
    FenwickTree(int _n) : n(_n) {
        ft.resize(n + 1);
    }

    void update(int i, ll x) {
        for(; i <= n; i += i & -i) {
            ft[i] += x;
        }
    }

    ll query(int i) {
        ll r = 0;

        for(; i; i -= i & -i) {
            r += ft[i];
        }

        return r;
    }
};

ll s, t;

inline ll dodaj(ll x, ll y) {
    ll raz = abs(x - y);

    if(x < y) return -raz * s;
    else return raz * t;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q;

    cin >> n >> q >> s >> t;

    vector<ll> v(n + 1);

    for(int i = 0; i <= n; ++i) {
        cin >> v[i];
    }

    ll ans = 0;

    FenwickTree ft(n);

    for(int i = 1; i <= n; ++i) {
        ans += dodaj(v[i - 1], v[i]);

        ft.update(i, v[i]);

        if(i + 1 <= n) {
            ft.update(i + 1, -v[i]);
        }
    }

    while (q--) {
        int l, r;
        ll x;

        cin >> l >> r >> x;

        ans -= dodaj(ft.query(l - 1), ft.query(l));

        if(r + 1 <= n) {
            ans -= dodaj(ft.query(r), ft.query(r + 1));
        }

        ft.update(l, x);
        ft.update(r + 1, -x);

        ans += dodaj(ft.query(l - 1), ft.query(l));

        if(r + 1 <= n) {
            ans += dodaj(ft.query(r), ft.query(r + 1));
        }

        cout << ans << '\n';

        // for(int i = 1; i <= n; ++i) {
        //     cerr << ft.query(i) << " ";
        // }

        // cerr << endl;
    }
}

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