Submission #523986

#	Time	Username	Problem	Language	Result	Execution time	Memory
523986		FireGhost1301	Foehn Phenomena (JOI17_foehn_phenomena)	C++11	100 / 100	251 ms	14052 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 3;
int n, q, s, t, a[N];
int sz;
long long seg[4 * N];

void init() {
    sz = 1;
    while (sz <= n + 1) sz <<= 1;
}

void build(int x = 0, int lx = 0, int rx = sz) {
    if (rx - lx == 1) {
        if (lx <= n) seg[x] = a[lx];
        return;
    }
    int mid = (lx + rx) >> 1;
    build(2 * x + 1, lx, mid);
    build(2 * x + 2, mid, rx);
}

void upd(int l, int r, int v, int x = 0, int lx = 0, int rx = sz) {
    if (lx >= r || rx <= l) return;
    if (lx >= l && rx <= r) {
        seg[x] += v;
        return;
    }
    int mid = (lx + rx) >> 1;
    upd(l, r, v, 2 * x + 1, lx, mid);
    upd(l, r, v, 2 * x + 2, mid, rx);
}

long long get(int p, int x = 0, int lx = 0, int rx = sz) {
    if (rx - lx == 1) return seg[x];
    int mid = (lx + rx) >> 1;
    long long ans = seg[x];
    if (p < mid) ans += get(p, 2 * x + 1, lx, mid);
    else ans += get(p, 2 * x + 2, mid, rx);
    return ans;
}

void solve() {
    cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; ++i)
        cin >> a[i];
    long long cur_ans = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] < a[i + 1]) cur_ans -= 1LL * s * (a[i + 1] - a[i]);
        else cur_ans += 1LL * t * (a[i] - a[i + 1]);
    }
    init(), build();
    while (q--) {
        int l, r, v; cin >> l >> r >> v;
        long long k1 = get(l - 1), k2 = get(l);
        long long z1 = get(r), z2 = LLONG_MIN;
        if (r != n) z2 = get(r + 1);
        upd(l, r + 1, v);
        if (k1 < k2) cur_ans += 1LL * s * (k2 - k1);
        else cur_ans -= 1LL * t * (k1 - k2);
        if (z2 != LLONG_MIN) {
            if (z1 < z2) cur_ans += 1LL * s * (z2 - z1);
            else cur_ans -= 1LL * t * (z1 - z2);
        }
        k2 += v, z1 += v;
        if (k1 < k2) cur_ans -= 1LL * s * (k2 - k1);
        else cur_ans += 1LL * t * (k1 - k2);
        if (z2 != LLONG_MIN) {
            if (z1 < z2) cur_ans -= 1LL * s * (z2 - z1);
            else cur_ans += 1LL * t * (z1 - z2);
        }
        cout << cur_ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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