Submission #916539

#	Time	Username	Problem	Language	Result	Execution time	Memory
916539		viwlesxq	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	859 ms	36672 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 1e9 + 7;

struct segtree {
    int n;
    vector<int> t, mdf;
    segtree(int n) {
        this -> n = n;
        t.assign(4 * n + 4, 0);
        mdf.assign(4 * n + 4, 0);
    }
    void push(int v, int tl, int tr) {
        t[v] += mdf[v] * (tr - tl + 1);
        if (tl != tr) {
            mdf[2 * v] += mdf[v];
            mdf[2 * v + 1] += mdf[v];
        }
        mdf[v] = 0;
    }
    void upd(int v, int tl, int tr, int l, int r, int delta) {
        if (mdf[v]) push(v, tl, tr);
        if (tl > r || tr < l) return;
        if (tl >= l && tr <= r) {
            mdf[v] += delta;
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        upd(2 * v, tl, tm, l, r, delta);
        upd(2 * v + 1, tm + 1, tr, l, r, delta);
        t[v] = t[2 * v] + t[2 * v + 1];
    } void upd(int l, int r, int delta) {
        upd(1, 1, n, l, r, delta);
    }
    int get(int v, int tl, int tr, int i) {
        if (mdf[v]) push(v, tl, tr);
        if (tl == tr) return t[v];
        int tm = (tl + tr) / 2;
        if (tm >= i) return get(2 * v, tl, tm, i);
        return get(2 * v + 1, tm + 1, tr, i);
    } int get(int i) {
        if (i < 1) return 0ll;
        return get(1, 1, n, i);
    }
};

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q, S, T;
    cin >> n >> q >> S >> T;
    int a[n + 1];
    for (int i = 0; i <= n; ++i) cin >> a[i];
    segtree t(n), h(n);
    int temp = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] < a[i - 1]) temp += (a[i - 1] - a[i]) * T;
        else temp -= (a[i] - a[i - 1]) * S;
        t.upd(i, i, temp);
        h.upd(i, i, a[i]);
    }
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        h.upd(l, r, x);
        int a = h.get(l - 1), b = h.get(l), c = t.get(l - 1), d = t.get(l);
        if (a < b) t.upd(l, r, c + (a - b) * S - d);
        else t.upd(l, r, c + (a - b) * T - d);
        if (r < n) {
            a = h.get(r), b = h.get(r + 1), c = t.get(r), d = t.get(r + 1);
            if (a < b) t.upd(r + 1, n, c + (a - b) * S - d);
            else t.upd(r + 1, n, c + (a - b) * T - d);
        }
        cout << t.get(n) << '\n';
    }
} 

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