Submission #837560

#	Time	Username	Problem	Language	Result	Execution time	Memory
837560		_martynas	Foehn Phenomena (JOI17_foehn_phenomena)	C++11	100 / 100	156 ms	7244 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mxn = 2e5+5;

int n, q;
ll s, t;
ll a[mxn], fen[mxn];
ll ans = 0;

void add(int i, int x) {
    while(i <= n) {
        fen[i] += x;
        i += i&(-i);
    }
}

ll get(int i) {
    ll ans = 0; while(i) {
        ans += fen[i];
        i -= i&(-i);
    } return ans;
}

ll diff_to_delta(ll diff) {
    return diff > 0 ? -s*diff : -t*diff;
}

int main(int argc, char const *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q >> s >> t;
    n++;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) {
        add(i, a[i+1]-a[i]);
        ans += diff_to_delta(a[i+1]-a[i]);
    }
    for(int i = 0; i < q; i++) {
        int l, r, x; cin >> l >> r >> x; l++, r++;
        if(l > 1) {
            ll diff = get(l-1)-(l-2 > 0 ? get(l-2) : 0);
            ans -= diff_to_delta(diff);
            add(l-1, x);
            diff = get(l-1)-(l-2 > 0 ? get(l-2) : 0);
            ans += diff_to_delta(diff);
        }
        if(r < n) {
            ll diff = get(r)-get(r-1);
            ans -= diff_to_delta(diff);
            add(r, -x);
            diff = get(r)-get(r-1);
            ans += diff_to_delta(diff);
        }
        cout << ans << "\n";
    }
    return 0;
}

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