Submission #632168

#	Time	Username	Problem	Language	Result	Execution time	Memory
632168		Ooops_sorry	Snowball (JOI21_ho_t2)	C++17	100 / 100	1069 ms	15300 KiB

Main

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const ll INF = 1e18;

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<ll> x(n), w(q), ans(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    ll cur = 0, mn = 0, mx = 0;
    vector<ll> u{-INF, INF};
    for (int i = 0; i < q; i++) {
        cin >> w[i];
        cur += w[i];
        mn = min(mn, cur);
        mx = max(mx, cur);
        u.pb(cur);
    }
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    int m = u.size();
    vector<int> pr(m, q), sf(m, q);
    cur = 0;
    for (int i = 0; i < q; i++) {
        cur += w[i];
        int j = lower_bound(u.begin(), u.end(), cur) - u.begin();
        pr[j] = min(pr[j], i);
        sf[j] = min(sf[j], i);
    }
    for (int i = 1; i < m; i++) {
        pr[i] = min(pr[i], pr[i - 1]);
    }
    for (int i = m - 2; i >= 0; i--) {
        sf[i] = min(sf[i], sf[i + 1]);
    }
    for (int i = 0; i + 1 < n; i++) {
        ll l = 0, r = x[i + 1] - x[i] + 1, d = x[i + 1] - x[i];
        if (abs(mn) + mx <= x[i + 1] - x[i]) {
            ans[i] += mx;
            ans[i + 1] += abs(mn);
            continue;
        }
        while (r - l > 1) {
            ll mid = (r + l) / 2;
            int j = lower_bound(u.begin(), u.end(), mid) - u.begin();
            int k = upper_bound(u.begin(), u.end(), -(d - mid + 1)) - u.begin() - 1;
            if (sf[j] < pr[k]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        ans[i] += l;
        ans[i + 1] += d - l;
    }
    ans[0] += abs(mn);
    ans.back() += abs(mx);
    for (int i = 0; i < n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

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