제출 #1159639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159639		Hakuna	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	217 ms	18888 KiB

foehn_phenomena

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

const int N = 2e5 + 5;
int n, Q, S, T;
long long a[N];
int id[N];

struct tree {
    long long ans{};
    long long sum{};
    int l{}, r{};
    
    tree() = default;
};
tree merge(tree a, tree b) {
    tree res;
    res.ans = a.ans + b.ans;
    res.sum = a.sum + b.sum;
    res.l = min(a.l, b.l);
    res.r = max(a.r, b.r);
    return res;
}

tree t[N<<2];
void build(int v, int l, int r) {
    if (l == r) {
        id[l] = v;
        if (r == n) {
            t[v].ans = 0;
        } else {
            if (a[r] < a[r + 1]) {
                t[v].ans = -S * (a[r + 1] - a[r]);
            } else {
                t[v].ans = T * (a[r] - a[r + 1]);
            }
        }
        t[v].l = l;
        t[v].r = r;
        return;
    }
    int m = l + r >> 1;
    build(v<<1, l, m);
    build(v<<1|1, m+1, r);
    t[v] = merge(t[v<<1], t[v<<1|1]);
}
long long get_val(int v, int l, int r, int i) {
    if (l > i) return 0;
    if (r <= i) return t[v].sum;
    int m = l+r >> 1;
    return get_val(v<<1, l, m, i) + get_val(v<<1|1, m+1, r, i);
}
void upd_tree(int v) {
    if (v > 0) t[v] = merge(t[v<<1], t[v<<1|1]);
    if (v > 1) upd_tree(v >> 1);
}
void upd(int v, int l, int r, int i, int x) {
    if (l == r) {
        t[v].sum += x;
        long long f = get_val(1, 0, n, r - 1);
        long long cur = f + t[v].sum + a[r];
        f += a[r - 1];
        if (f < cur) {
            t[id[r - 1]].ans = -S * (cur - f);
        } else {
            t[id[r - 1]].ans = T * (f - cur);
        }
        upd_tree(id[r - 1] >> 1);
        return;
    }
    int m = l+r >> 1;
    if (i <= m) {
        upd(v<<1, l, m, i, x);
    } else {
        upd(v<<1|1, m+1, r, i, x);
    }
    t[v] = merge(t[v<<1], t[v<<1|1]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> Q >> S >> T;
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 0, n);
    while (Q--) {
        int l, r, x;
        cin >> l >> r >> x;
        
        if (r + 1 <= n)
            upd(1, 0, n, r + 1, -x);
        upd(1, 0, n, l, x);
        
        cout << t[1].ans << '\n';
    }

    return 0;
}

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