제출 #1279838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279838		MinhKien	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	189 ms	9888 KiB

foehn_phenomena

#include <iostream>

using namespace std;

#define ll long long

const int N = 2e5 + 10;

int n, m;
ll A, B, a[N];
ll low, high;

struct SEG {
    ll val[N <<  2];

    void build(int l, int r, int id) {
        if (l == r) {
            val[id] = a[l];
            return;
        }

        int mid = (l + r) >> 1;
        build(l, mid, id << 1);
        build(mid + 1, r, id << 1 | 1);

        val[id] = 0;
    }

    void down(int id) {
        if (!val[id]) return;
        val[id << 1] += val[id];
        val[id << 1 | 1] += val[id];
        val[id] = 0;
    }

    void update(int l, int r, int u, int v, ll VAL, int id) {
        if (l > v || r < u) return;

        if (l >= u && r <= v) {
            val[id] += VAL;
            return;
        }

        int mid = (l + r) >> 1;
        down(id);
        update(l, mid, u, v, VAL, id << 1);
        update(mid + 1, r, u, v, VAL, id << 1 | 1);
    }

    ll get(int l, int r, int u, int id) {
        if (u == 0) return 0;
        if (l == r) return val[id];

        int mid = (l + r) >> 1;
        down(id);
        if (u <= mid) return get(l, mid, u, id << 1);
        return get(mid + 1, r, u, id << 1 | 1);
    }
} seg;

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> A >> B;
    for (int i = 0; i <= n; ++i) {
        cin >> a[i];

        if (a[i] > a[i - 1]) {
            high += a[i] - a[i - 1];
        } else {
            low += a[i - 1] - a[i];
        }
    }
    seg.build(1, n, 1);

    int l, r;
    ll w;
    while (m--) {
        cin >> l >> r >> w;

        ll curL = seg.get(1, n, l, 1), bL = seg.get(1, n, l - 1, 1);
        if (curL > bL) {
            high -= (curL - bL);
        } else {
            low -= (bL - curL);
        }

        ll curR, aR;
        if (r != n) {
            curR = seg.get(1, n, r, 1), aR = seg.get(1, n, r + 1, 1);
            if (aR > curR) {
                high -= (aR - curR);
            } else {
                low -= (curR - aR);
            }
        }

        seg.update(1, n, l, r, w, 1);

        curL += w;
        if (curL > bL) {
            high += (curL - bL);
        } else {
            low += (bL - curL);
        }

        if (r != n) {
            curR += w;
            if (aR > curR) {
                high += (aR - curR);
            } else {
                low += (curR - aR);
            }
        }

        cout << low * B - high * A << "\n";
    }

    return 0;
}

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