Submission #706155

#	Time	Username	Problem	Language	Result	Execution time	Memory
706155		Pring	Snowball (JOI21_ho_t2)	C++14	0 / 100	2 ms	468 KiB

Main

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

#define int long long
typedef pair<int, int> pii;

struct P {
    int el, er;
    int val() {
        return el + er;
    }
};

const int MXN = 200005;

int n, q, a[MXN], w[MXN], wei[MXN], dil, bound;
P p[MXN];
vector<int> v;

void getP() {
    int now = 0;
    v.push_back(0);
    for (int i = 0; i < q; i++) {
        now += w[i];
        if (v.back() >= 0 && now > v.back()) v.pop_back();
        else if (v.back() <= 0 && now < v.back()) v.pop_back();
        v.push_back(now);
    }
    dil = v.size();
    P pp = {0, 0};
    for (int i = 0; i < dil; i++) {
        if (v[i] > 0) pp.el = v[i];
        else pp.er = -v[i];
        p[i] = pp;
    }
    bound = pp.val();
}

void solve(int id) {
    int space = a[id] - a[id - 1];
    P pp;
    if (space > bound) {
        pp = p[dil - 1];
    } else {
        auto it = lower_bound(p, p + dil, space, [](P a, int b) {
            return a.val() < b;
        });
        P pb = *it;
        it--;
        P pa = *it;
        pp = pa;
        int x = space - pa.val();
        if (pa.el == pb.el) {
            pp.er += x;
        } else {
            pp.el += x;
        }
    }
    wei[id - 1] += pp.el;
    wei[id] += pp.er;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> w[i];
    getP();
    // for (int i = 0; i < dil; i++) cout << v[i] << ' ';
    // cout << endl;
    for (int i = 1; i < n; i++) {
        solve(i);
    }
    wei[0] += p[dil - 1].er;
    wei[n - 1] += p[dil - 1].el;
    for (int i = 0; i < n; i++) cout << wei[i] << '\n';
    return 0;
}

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