Submission #894203

#	Time	Username	Problem	Language	Result	Execution time	Memory
894203		box	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	91 ms	10832 KiB

ho_t1

#include "bits/stdc++.h"

using namespace std;

const int N = 2e5 + 5;

int n, a[N], b[N];
int p[N], o[N], pf[N], sf[N];

int main() {
    cin.tie(0)->sync_with_stdio(0), cin.exceptions(cin.failbit);
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i], p[i] = i;
    for (int i = 0; i < n; i++) cin >> b[i];
    sort(p, p + n + 1, [ & ](int i, int j) {
        return a[i] < a[j];
    });
    for (int i = 0; i <= n; i++) o[p[i]] = i;
    sort(b, b + n);
    for (int i = 0; i < n; i++) pf[i] = max(i > 0 ? pf[i - 1] : 0, max(a[p[i]] - b[i], 0));
    for (int i = n; i >= 1; i--) sf[i] = max(i < n ? sf[i + 1] : 0, max(a[p[i]] - b[i - 1], 0));
    for (int i = 0; i <= n; i++) {
        int j = o[i];
        cout << max(j > 0 ? pf[j - 1] : 0, j < n ? sf[j + 1] : 0) << " \n" [i == n];
    }
}

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