Submission #541497

#TimeUsernameProblemLanguageResultExecution timeMemory
541497NyanCatTW1Just Long Neckties (JOI20_ho_t1)C++17
100 / 100
257 ms21760 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
typedef long long LL;

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

    int N;
    cin >> N;

    vector<pair<LL, int> > A(N + 1);
    vector<LL> B(N);
    for (int i = 0; i <= N; i++) {
        cin >> A[i].first;
        A[i].second = i;
    }

    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    multiset<LL> vals;
    for (int i = 0; i < N; i++) {
        // After - Before;
        vals.insert(max(A[i + 1].first - B[i], 0LL));
    }

    vector<LL> ans(N + 1);
    for (int i = 0; i <= N; i++) {
        if (i) {
            vals.erase(vals.find(max(A[i].first - B[i - 1], 0LL)));
            vals.insert(max(A[i - 1].first - B[i - 1], 0LL));
        }

        ans[A[i].second] = *vals.rbegin();
    }

    for (int i = 0; i <= N; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }

    cout << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...