Submission #991167

#	Time	Username	Problem	Language	Result	Execution time	Memory
991167		aaaaaarroz	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	350 ms	16980 KiB

foehn_phenomena

#include<bits/stdc++.h>
const char nl = '\n';
using namespace std;
using ll = long long;
ll s, t;
struct Segtree {
    struct node {
        ll le, ri, wd;
    };
    vector<ll> tree;
    vector<ll> sh;
    vector<ll> a;
    ll sz = 1;
    ll nope = 0;
    void init(ll n) {
        while (sz < n) {
            sz *= 2;
        }
        tree.assign(2*sz+1, 0);
        sh.assign(2*sz+1, 0);
        a.assign(n+10, 0);
    }
    void create(ll n) {
        for (ll i = 0, lf = sz-1; i <= n; i ++, lf ++) {
            tree[lf] = a[i];
        }
    }
    void build(ll x, ll lx, ll rx) {
        if (rx - lx == 1) {
            return ;
        }
        ll mid = (lx + rx) / 2;
        build(2*x+1, lx, mid);
        build(2*x+2, mid, rx);
        tree[x] = tree[2*x+1] + tree[2*x+2];
    }
    void build() {
        build(0, 0, sz);
    }
    void push(ll x, ll lx, ll rx) {
        if (sh[x] == nope) return ;
        if (rx - lx == 1) return ;
        sh[2*x+1] += sh[x];
        tree[2*x+1] += sh[x];
        sh[2*x+2] += sh[x];
        tree[2*x+2] += sh[x];
        sh[x] = nope;
    }
    void update(ll l, ll r, ll v, ll x, ll lx, ll rx) {
        push(x, lx, rx);
        if (lx >= r || rx <= l) {
            return ;
        }
        if (l <= lx && rx <= r) {
            sh[x] += v;
            push(x, lx, rx);
            tree[x] += v;
            return ;
        }
        ll mid = (lx + rx) / 2;
        update(l, r, v, 2*x+1, lx, mid);
        update(l, r, v, 2*x+2, mid, rx);
        tree[x] = tree[2*x+1] + tree[2*x+2];
    }
    void update(ll l, ll r, ll v) {
        update(l, r, v, 0, 0, sz);
    }
    ll get(ll i, ll x, ll lx, ll rx) {
        push(x, lx, rx);
        if (rx - lx == 1) {
            return tree[x];
        }
        ll mid = (lx + rx) / 2;
        if (i < mid) {
            return get(i, 2*x+1, lx, mid);
        } else {
            return get(i, 2*x+2, mid, rx);
        }
    } 
    ll get(ll i) {
        return get(i, 0, 0, sz);
    }
    void debug() {
        for (ll i = 0; i < 2*sz-1; i ++) {
            cout << i << ": " << tree[i] << nl;
        }
    }
};
ll wind(ll x, ll y) {
    return (x < y ? s * (x - y) : t * (x - y));
}
void solve() {
    ll n, q;
    cin >> n >> q >> s >> t;
    Segtree sg;
    n ++;
    sg.init(n);
    for (ll i = 0; i < n; i ++) {
        cin >> sg.a[i];
    }
    sg.create(n);
    sg.build();
    ll res = 0;
    for (ll i = 0; i < n-1; i ++) {
        res += wind(sg.a[i], sg.a[i+1]);
    }
    for (ll i = 0; i < q; i ++) {
        ll l, r, v;
        cin >> l >> r >> v;
        r ++;
        res -= wind(sg.get(l-1), sg.get(l));
        if (r != n) {
            res -= wind(sg.get(r-1), sg.get(r));
        }
        sg.update(l, r, v);
        res += wind(sg.get(l-1), sg.get(l));
        if (r != n) {
            res += wind(sg.get(r-1), sg.get(r));
        }	
        cout << res << nl;	
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll tst = 1;
    while (tst --) {
        solve();
        cout << nl;
    }
}

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