Submission #901420

#	Time	Username	Problem	Language	Result	Execution time	Memory
901420		Blagoj	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	476 ms	24068 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 2e5 + 10;

ll a[mxn];

struct SegmentTree {
    vector<ll> sgt, lz;

    SegmentTree(int sz) {
        sgt.resize(4 * sz);
        lz.resize(4 * sz);
    }

    void build(int k, int l, int r) {
        if (l == r) {
            sgt[k] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m);
        build(k * 2 + 1, m + 1, r);
    }

    void push(int k, int l, int r) {
        if (lz[k]) {
            sgt[k] += lz[k];
            if (l != r) {
                lz[k * 2] += lz[k];
                lz[k * 2 + 1] += lz[k];
            }
            lz[k] = 0;
        }
    }

    void update(int k, int l, int r, int i, int j, ll val) {
        push(k, l, r);
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            lz[k] += val;
            push(k, l, r);
            return;
        }
        int m = (l + r) / 2;
        update(k * 2, l, m, i, j, val);
        update(k * 2 + 1, m + 1, r, i, j, val);
    }

    ll get(int k, int l, int r, int i) {
        push(k, l, r);
        if (l == r) return sgt[k];
        int m = (l + r) / 2;
        if (m >= i) return get(k * 2, l, m, i);
        return get(k * 2 + 1, m + 1, r, i);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    n++;
    for (int i = 0; i < n; i++) cin >> a[i];
    SegmentTree sgt(n);
    sgt.build(1, 0, n - 1);
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        if (a[i - 1] < a[i]) ans += (a[i] - a[i - 1]) * s;
        else ans += (a[i] - a[i - 1]) * t;
    }
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
    
        a[l - 1] = sgt.get(1, 0, n - 1, l - 1);
        a[l] = sgt.get(1, 0, n - 1, l);
        if (a[l - 1] < a[l]) ans -= (a[l] - a[l - 1]) * s;
        else ans -= (a[l] - a[l - 1]) * t;
        if (l < n - 1) {
            a[l + 1] = sgt.get(1, 0, n - 1, l + 1);
            if (a[l] < a[l + 1]) ans -= (a[l + 1] - a[l]) * s;
            else ans -= (a[l + 1] - a[l]) * t;
        }


        if (l != r) {
            if (l + 1 < r) {
                a[r - 1] = sgt.get(1, 0, n - 1, r - 1);
                a[r] = sgt.get(1, 0, n - 1, r);
                if (a[r - 1] < a[r]) ans -= (a[r] - a[r - 1]) * s;
                else ans -= (a[r] - a[r - 1]) * t;
            }
            if (r < n - 1) {
                a[r + 1] = sgt.get(1, 0, n - 1, r + 1);
                if (a[r] < a[r + 1]) ans -= (a[r + 1] - a[r]) * s;
                else ans -= (a[r + 1] - a[r]) * t;
            }
        }

        sgt.update(1, 0, n - 1, l, r, x);

        a[l - 1] = sgt.get(1, 0, n - 1, l - 1);
        a[l] = sgt.get(1, 0, n - 1, l);
        if (a[l - 1] < a[l]) ans += (a[l] - a[l - 1]) * s;
        else ans += (a[l] - a[l - 1]) * t;
        if (l < n - 1) {
            a[l + 1] = sgt.get(1, 0, n - 1, l + 1);
            if (a[l] < a[l + 1]) ans += (a[l + 1] - a[l]) * s;
            else ans += (a[l + 1] - a[l]) * t;
        }

        if (l != r) {
            if (l + 1 < r) {
                a[r - 1] = sgt.get(1, 0, n - 1, r - 1);
                a[r] = sgt.get(1, 0, n - 1, r);
                if (a[r - 1] < a[r]) ans += (a[r] - a[r - 1]) * s;
                else ans += (a[r] - a[r - 1]) * t;
            }
            if (r < n - 1) {
                a[r + 1] = sgt.get(1, 0, n - 1, r + 1);
                if (a[r] < a[r + 1]) ans += (a[r + 1] - a[r]) * s;
                else ans += (a[r + 1] - a[r]) * t;
            }
        }

        cout << -ans << endl;
    }
}

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