Submission #733494

#	Time	Username	Problem	Language	Result	Execution time	Memory
733494		Pring	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	261 ms	19532 KiB

ho_t1

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

#define int long long
typedef pair<int, int> pii;

const int MXN = 200005;
int n, C[MXN];
pii a[MXN], b[MXN];
multiset<int> MS;

int f(int a, int b) {
    return max(0LL, a - b);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> 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].first;
        b[i].second = i;
    }
    sort(a, a + n + 1);
    sort(b, b + n);
    for (int i = 0; i < n; i++) {
        MS.insert(f(a[i].first, b[i].first));
    }
    C[a[n].second] = *MS.rbegin();
    for (int i = n - 1; i >= 0; i--) {
        MS.erase(MS.find(f(a[i].first, b[i].first)));
        MS.insert(f(a[i + 1].first, b[i].first));
        C[a[i].second] = *MS.rbegin();
    }
    for (int i = 0; i <= n; i++) cout << C[i] << ' ';
    cout << endl;
    return 0;
}

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