Submission #556089

#	Time	Username	Problem	Language	Result	Execution time	Memory
556089		alextodoran	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	261 ms	19404 KiB

ho_t1

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N;
int A[N_MAX + 2];
int B[N_MAX + 2];

int p[N_MAX + 2];
int id[N_MAX + 2];

int answer[N_MAX + 2];

multiset <int> s;

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

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

    iota(p + 1, p + (N + 1) + 1, 1);
    sort(p + 1, p + (N + 1) + 1, [&] (const int &i, const int &j) {
        return A[i] < A[j];
    });
    sort(B + 1, B + N + 1);

    for (int i = 1; i <= (N + 1); i++) {
        id[p[i]] = i;
    }
    sort(A + 1, A + (N + 1) + 1);

    for (int i = 1; i <= N; i++) {
        s.insert(max(0, A[i + 1] - B[i]));
    }
    for (int i = 1; i <= N + 1; i++) {
        answer[i] = *s.rbegin();
        if (i <= N) {
            s.erase(s.find(max(0, A[i + 1] - B[i])));
            s.insert(max(0, A[i] - B[i]));
        }
    }
    for (int i = 1; i <= N + 1; i++) {
        cout << answer[id[i]] << " ";
    }
    cout << "\n";

    return 0;
}

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