Submission #870025

#	Time	Username	Problem	Language	Result	Execution time	Memory
870025		Pannda	Snowball (JOI21_ho_t2)	C++17	100 / 100	115 ms	8520 KiB

Main

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T;
    cin >> n >> T;
    T++;

    vector<long long> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    vector<long long> delta(T, 0);
    vector<long long> mx(T, 0), mn(T, 0);
    for (int t = 1; t < T; t++) {
        long long d;
        cin >> d;
        delta[t] = delta[t - 1] + d;
        mx[t] = max(mx[t - 1], delta[t]);
        mn[t] = min(mn[t - 1], delta[t]);
    }

    auto getL = [&](int i) {
        if (i == 0 || x[i - 1] + mx.back() <= x[i] + mn.back()) return x[i] + mn.back();
        int l = 0, r = T - 1;
        while (l < r) {
            int t = (l + r + 1) >> 1;
            if (x[i - 1] + mx[t] <= x[i] + mn[t]) {
                l = t;
            } else {
                r = t - 1;
            }
        }
        assert(l != T - 1);
        if (x[i - 1] + mx[l + 1] > x[i] + mn[l]) return x[i] + mn[l];
        if (x[i - 1] + mx[l] > x[i] + mn[l + 1]) return x[i - 1] + mx[l];
        assert(false);
    };

    auto getR = [&](int i) {
        if (i == n - 1 || x[i] + mx.back() <= x[i + 1] + mn.back()) return x[i] + mx.back();
        int l = 0, r = T - 1;
        while (l < r) {
            int t = (l + r + 1) >> 1;
            if (x[i] + mx[t] <= x[i + 1] + mn[t]) {
                l = t;
            } else {
                r = t - 1;
            }
        }
        assert(l != T - 1);
        if (x[i] + mx[l + 1] > x[i + 1] + mn[l]) return x[i + 1] + mn[l];
        if (x[i] + mx[l] > x[i + 1] + mn[l + 1]) return x[i] + mx[l];
        assert(false);
    };

    for (int i = 0; i < n; i++) {
        cout << getR(i) - getL(i) << '\n';
    }
}

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