Submission #541497

#	Time	Username	Problem	Language	Result	Execution time	Memory
541497		NyanCatTW1	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	257 ms	21760 KiB

ho_t1

#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';
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91