Submission #1295277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295277		kawhiet	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	10 / 100	289 ms	13360 KiB

foehn_phenomena

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

#define int long long

constexpr int N = 2e5 + 5;

int n;
int t[4 * N], lz[4 * N], a[N];

void push(int id, int tl, int tr) {
    if (tl == tr || !lz[id]) return;
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    lz[x] += lz[id];
    lz[y] += lz[id];
    t[x] += (tm - tl + 1) * lz[id];
    t[y] += (tr - tm) * lz[id];
}

void update(int id, int tl, int tr, int l, int r, int k) {
    push(id, tl, tr);
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) {
        lz[id] += k;
        t[id] += (tr - tl + 1) * k;
        push(id, tl, tr);
        return;
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    update(x, tl, tm, l, r, k);
    update(y, tm + 1, tr, l, r, k);
    t[id] = t[x] + t[y];
}

int get(int id, int tl, int tr, int i) {
    push(id, tl, tr);
    if (tl == tr) {
        return t[id];
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    if (i <= tm) {
        return get(x, tl, tm, i);
    } else {
        return get(y, tm + 1, tr, i);
    }
}

void update(int l, int r, int k) { update(0, 0, n + 1, l, r, k); }
int get(int i) { return get(0, 0, n + 1, i); }

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q, s, t;
    cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
        update(0, 0, n + 1, i, i, a[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < a[i + 1]) {
            res -= s * (a[i + 1] - a[i]);
        } else {
            res += t * (a[i] - a[i + 1]);
        }
    }
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        int x = get(l - 1), y = get(l);
        if (x < y) {
            res += s * (y - x);
        } else {
            res -= t * (x - y);
        }
        y += k;
        if (x < y) {
            res -= (y - x) * s;
        } else {
            res += (x - y) * t;
        }
        if (r < n) {
            x = get(r), y = get(r + 1);
            if (x < y) {
                res += s * (y - x);
            } else {
                res -= t * (x - y);
            }
            x += k;
            if (x < y) {
                res -= (y - x) * s;
            } else {
                res += (x - y) * t;
            }
        }
        update(l, r, k);
        cout << res << '\n';
    }
    return 0;
}

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