Submission #999076

#	Time	Username	Problem	Language	Result	Execution time	Memory
999076		coolboy19521	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	267 ms	28768 KiB

foehn_phenomena

#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"

#define int long long

using namespace std;

const int sz = 2e5 + 10;

int st[sz * 8], lz[sz * 8], a[sz], b[sz];

void build(int le, int ri, int v) {
    if (le == ri) {
        st[v] = a[le];
        return;
    }
    int mi = le + (ri - le) / 2;
    build(le, mi, v * 2);
    build(mi + 1, ri, v * 2 + 1);
}

void relax(int v) {
    st[v] += lz[v];
    lz[v * 2] += lz[v];
    lz[v * 2 + 1] += lz[v];
    lz[v] = 0;
}

void update(int le, int ri, int ql, int qr, int v, int k) {
    if (le > qr || ri < ql) return;
    if (ql <= le && ri <= qr) {
        lz[v] += k;
        relax(v);
        return;
    }
    int mi = le + (ri - le) / 2;
    update(le, mi, ql, qr, v * 2, k);
    update(mi + 1, ri, ql, qr, v * 2 + 1, k);
}

int query(int le, int ri, int ql, int qr, int v) {
    relax(v);
    if (le > qr || ri < ql) return 0;
    if (ql <= le && ri <= qr) {
        a[le] = st[v];
        return st[v];
    }
    int mi = le + (ri - le) / 2;
    int lq = query(le, mi, ql, qr, v * 2);
    int rq = query(mi + 1, ri, ql, qr, v * 2 + 1);
    return lq + rq;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, q, s, t;
    cin >> n >> q >> s >> t;

    int tm;
    cin >> tm;

    int r = 0;

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        int d = a[i - 1] - a[i];
        if (0 < d) {
            b[i] = d * t;
        } else {
            b[i] = d * s;
        }
        r += b[i];
    }

    build(1, n, 1);

    while (q --) {
        int le, ri, x;
        cin >> le >> ri >> x;
        update(1, n, le, ri, 1, x);
        query(1, n, le, le, 1);
        query(1, n, ri, ri, 1);
        query(1, n, le - 1, le - 1, 1);
        if (ri + 1 <= n) {
            query(1, n, ri + 1, ri + 1, 1);
        }
        // cout << a[le] << ' ' << a[ri] << '\n';
        r -= b[le];
        int d = a[le - 1] - a[le];
        if (0 < d) {
            b[le] = d * t;
        } else {
            b[le] = d * s;
        }
        if (ri + 1 <= n) {
            d = a[ri] - a[ri + 1];
            r -= b[ri + 1];
            if (0 < d) {
                b[ri + 1] = d * t;
            } else {
                b[ri + 1] = d * s;
            }
            r += b[ri + 1];
        }
        r += b[le];
        cout << r << '\n';
    }
}

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