Submission #996677

#	Time	Username	Problem	Language	Result	Execution time	Memory
996677		overwatch9	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	665 ms	29012 KiB

foehn_phenomena

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
struct node {
    ll val = 0;
    bool pd = false;
    ll lz = 0;
};
struct stree {
    #define lc v*2
    #define rc v*2+1
    vector <node> tree;
    stree (int s) {
        tree.resize(s * 4);
    }
    void pushdown(int v) {
        if (!tree[v].pd)
            return;
        tree[v].pd = false;
        tree[lc].pd = tree[rc].pd = true;
        tree[lc].lz += tree[v].lz;
        tree[rc].lz += tree[v].lz;
        tree[v].lz = 0;
    }
    void update(int v, int tl, int tr, int l, int r, ll delta) {
        if (tl > r || tr < l)
            return;
        if (tl >= l && tr <= r) {
            tree[v].lz += delta;
            tree[v].pd = true;
            return;
        }
        pushdown(v);
        int tm = (tl + tr) / 2;
        update(lc, tl, tm, l, r, delta);
        update(rc, tm+1, tr, l, r, delta);
    }
    ll query(int v, int tl, int tr, int p) {
        if (tl == tr)
            return tree[v].lz + tree[v].val;
        pushdown(v);
        int tm = (tl + tr) / 2;
        if (tm >= p && tl <= p)
            return query(lc, tl, tm, p);
        else
            return query(rc, tm+1, tr, p);
    }
};
int main() {
    int N, Q;
    ll S, T;
    cin >> N >> Q >> S >> T;
    vector <ll> a(N+1);
    for (int i = 0; i <= N; i++)
        cin >> a[i];
    stree tree(N+3);
    int sz = N+2;
    for (int i = 0; i <= N; i++)
        tree.update(1, 0, sz, i, i, a[i]);
    ll ans = 0;
    for (int i = 0; i+1 <= N; i++) {
        if (a[i] < a[i+1])
            ans -= S * (a[i+1] - a[i]);
        else
            ans += T * (a[i] - a[i+1]);
    }
    while (Q--) {
        int l, r, x;
        cin >> l >> r >> x;
        ll a = tree.query(1, 0, sz, l-1);
        ll b = tree.query(1, 0, sz, l);
        ll c = tree.query(1, 0, sz, r);
        ll d = tree.query(1, 0, sz, r+1);
        if (a < b)
            ans += S * (b - a);
        else
            ans -= T * (a - b);
        if (r+1 <= N) {
            if (c < d)
                ans += S * (d - c);
            else
                ans -= T * (c - d);
        }

        b += x;
        c += x;

        if (a < b)
            ans -= S * (b - a);
        else
            ans += T * (a - b);
        
        if (r+1 <= N) {
            if (c < d)
                ans -= S * (d - c);
            else
                ans += T * (c - d);
        }
        
        tree.update(1, 0, sz, l, r, x);
        cout << ans << '\n';
    }
}

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