Submission #659388

#	Time	Username	Problem	Language	Result	Execution time	Memory
659388		GrandTiger1729	Snowball (JOI21_ho_t2)	C++17	100 / 100	216 ms	37440 KiB

Main

#include <iostream>
#include <vector>
using namespace std;

const long long INF = 2e18;
struct segTree{
    int l, r, mid;
    long long val = 0, lz = 0;
    segTree *lc, *rc;
    segTree(vector<long long> &a, int _l, int _r): l(_l), r(_r){
        mid = (l + r) / 2;
        if (l == r - 1){
            val = a[l];
            return;
        }
        lc = new segTree(a, l, mid);
        rc = new segTree(a, mid, r);
        pull();
    }
    long long real_val(){
        return val + lz;
    }
    void pull(){
        val = min(lc->real_val(), rc->real_val());
    }
    void push(){
        if (lz != 0){
            lc->lz += lz;
            rc->lz += lz;
            lz = 0;
        }
        pull();
    }
    void update(int ll, int rr, long long u){
        if (ll <= l && rr >= r){
            lz -= u;
            return;
        }
        push();
        if (ll < mid){
            lc->update(ll, rr, u);
        }
        if (mid < rr){
            rc->update(ll, rr, u);
        }
        pull();
    }
    void query(vector<int> &ans){
        if (real_val() > 0){
            return;
        }
        if (l == r - 1){
            ans.push_back(l);
            val = INF;
            return;
        }
        push();
        lc->query(ans);
        rc->query(ans);
        pull();
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    vector<long long> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<long long> b(n + 1, INF);
    for (int i = 1; i < n; i++){
        b[i] = a[i] - a[i - 1];
    }
    segTree st(b, 0, n + 1);
    long long cur = 0, ll = 0, rr = 0;
    vector<long long> ans(n);
    vector<bool> vis(n + 1);
    while (q--){
        long long x; cin >> x;
        cur += x;
        if (x > 0 && cur > rr){
            st.update(0, n + 1, cur - rr);
            rr = cur;
            vector<int> res;
            st.query(res);
            for (auto &i: res){
                ans[i] += ll;
                ans[i - 1] += b[i] - ll;
                vis[i] = 1;
            }
        }
        if (x < 0 && -cur > ll){
            st.update(0, n + 1, -cur - ll);
            ll = -cur;
            vector<int> res;
            st.query(res);
            for (auto &i: res){
                ans[i - 1] += rr;
                ans[i] += b[i] - rr;
                vis[i] = 1;
            }
        }
    }
    ans[0] += ll;
    ans[n - 1] += rr;
    for (int i = 1; i < n; i++){
        if (!vis[i]){
            ans[i - 1] += rr;
            ans[i] += ll;
        }
    }
    for (int i = 0; i < n; i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67