Submission #1179578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179578		M_W_13	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	111 ms	7336 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 1 << 19;
ll A, B;
ll dp[2 * MAXN];
ll ans = 0;

void upd(int l, int r, ll x) {
    l += MAXN;
    r += MAXN;
    while (l < r) {
        if (l % 2 == 1) {
            dp[l] += x;
            l++;
        }
        if (r % 2 == 0) {
            dp[r] += x;
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        dp[l] += x;
    }
}

ll query(int v) {
    v += MAXN;
    ll odp = 0;
    while (v > 0) {
        odp += dp[v];
        v /= 2;
    }
    return odp;
}

ll policz(int i) {
    ll X = query(i);
    ll Y = query(i + 1);
    // cout << "X = " << X << " Y = " << Y << '\n';
    if (X < Y) {
        return ((X - Y) * A);
    }
    return ((X - Y) * B);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q;
    cin >> n >> q >> A >> B;
    n++;
    ll x;
    cin >> x;
    upd(0, 0, x);
    rep(i, n - 1) {
        cin >> x;
        upd(i + 1, i + 1, x);
        // cout << policz(i) << '\n';
        ans += policz(i);
    }
    // cout << "ans = " << ans << '\n';
    while (q--) {
        int l, r;
        cin >> l >> r >> x;
        if (l > 0) {
            ans -= policz(l - 1);
        }
        if (r + 1 < n) {
            ans -= policz(r);
        }
        upd(l, r, x);
        if (l > 0) {
            ans += policz(l - 1);
        }
        if (r + 1 < n) {
            ans += policz(r);
        }
        cout << ans << '\n';
    }
    return 0;
}

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