Submission #1341953

#TimeUsernameProblemLanguageResultExecution timeMemory
1341953PakinDioxideFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
97 ms7368 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 2e5+5;

int n, q;
ll fen[mxN], a[mxN], S, T;

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

ll qr(int idx) {
    ll x = 0;
    for (int i = idx; i > 0; i -= i & -i) x += fen[i];
    return x;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q >> S >> T;
    cin >> a[0];
    for (int i = 1; i <= n; i++) cin >> a[i], upd(i, a[i] - a[i-1]);
    ll curr = 0;
    auto calc = [&] (ll x, ll y) {
        if (y > x) return (x - y) * S;
        else return (x - y) * T;
    };
    for (int i = 1; i <= n; i++) curr += calc(a[i-1], a[i]);
    while (q--) {
        int l, r; cin >> l >> r;
        ll x; cin >> x;
        curr -= calc(qr(l-1), qr(l));
        if (r < n) curr -= calc(qr(r), qr(r+1));
        upd(l, x);
        if (r < n) upd(r+1, -x);
        curr += calc(qr(l-1), qr(l));
        if (r < n) curr += calc(qr(r), qr(r+1));
        cout << curr << '\n';
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...