Submission #224408

#	Time	Username	Problem	Language	Result	Execution time	Memory
224408		DS007	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	653 ms	24188 KiB

foehn_phenomena

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

const int N = 2e5 + 5;

class seg_tree {
    int *t, *lazy;
    int n;

public:
    seg_tree() {
        t = new int[1];
        lazy = new int[1];
    }

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

        int mid = (l + r) / 2;
        build(v * 2, l, mid, a);
        build(v * 2 + 1, mid + 1, r, a);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }

    void build(int n_, int a[]) {
        n = n_;
        t = new int[n * 8 + 8];
        lazy = new int[n * 8 + 8];

        build(1, 0, n, a);
        fill(lazy, lazy + 4 * n, 0);
    }

    void push_down(int v, int l, int r) {
        t[v] += lazy[v] * (r - l + 1);
        lazy[v * 2] += lazy[v];
        lazy[v * 2 + 1] += lazy[v];
        lazy[v] = 0;
    }

    int query(int v, int l, int r, int tl) {
        push_down(v, l, r);
        if (l == r && l == tl)
            return t[v];
        int mid = (l + r) / 2;
        if (tl <= mid)
            return query(v * 2, l, mid, tl);
        else
            return query(v * 2 + 1, mid + 1, r, tl);
    }

    void update(int v, int l, int r, int tl, int tr, int x) {
        push_down(v, l, r);
        if (tl > tr) {
            return;
        } else if (l == tl && r == tr) {
            lazy[v] += x;
            push_down(v, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(v * 2, l, mid, tl, min(tr, mid), x);
        update(v * 2 + 1, mid + 1, r, max(mid + 1, tl), tr, x);
    }
};

int n, q, s, t, cur;
int a[N];
seg_tree st;

void adjust(int x, int y, int off) {
    if (x < y)
        cur -= off * s * (y - x);
    else
        cur += off * t * (x - y);
}

void solveTestCase() {
    cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; i++) cin >> a[i];
    st.build(n, a);

    for (int i = 1; i <= n; i++)
        adjust(a[i - 1], a[i], 1);

    for (int i = 0; i < q; i++) {
        int l, r, x;
        cin >> l >> r >> x;

        int left = st.query(1, 0, n, l - 1), pl = st.query(1, 0, n, l), cl = pl + x;
        adjust(left, pl, -1);
        adjust(left, cl, 1);

        if (r != n) {
            int right = st.query(1, 0, n, r + 1), pr = st.query(1, 0, n, r), cr = pr + x;
            adjust(pr, right, -1);
            adjust(cr, right, 1);
        }

        st.update(1, 0, n, l, r, x);
        cout << cur << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase();
}

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