Submission #384952

#	Time	Username	Problem	Language	Result	Execution time	Memory
384952		timmyfeng	Snowball (JOI21_ho_t2)	C++17	100 / 100	125 ms	12268 KiB

Main

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

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

    int n, q;
    cin >> n >> q;

    vector<long long> x(n);
    for (auto &i : x) {
        cin >> i;
    }

    long long total = 0;
    vector<long long> left(q + 1), right(q + 1);
    for (int i = 0; i < q; ++i) {
        long long w;
        cin >> w;
        total += w;
        left[i + 1] = max(-total, left[i]);
        right[i + 1] = max(total, right[i]);
    }

    long long prv = left[q];
    for (int i = 1; i < n; ++i) {
        int low = 0, high = q;
        while (low < high) {
            int mid = (low + high + 1) / 2;
            if (left[mid] + right[mid] <= x[i] - x[i - 1]) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }

        if (high == q) {
            cout << prv + right[q] << "\n";
            prv = left[q];
        } else if (left[high] == left[high + 1]) {
            cout << prv + x[i] - x[i - 1] - left[high] << "\n";
            prv = left[high];
        } else {
            cout << prv + right[high] << "\n";
            prv = x[i] - x[i - 1] - right[high];
        }
    }

    cout << prv + right[q] << "\n";
}

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