【題解】LibreOJ #3252. 「JOI 2020 Final」只不过是长的领带

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 200005;
int n, b[maxn], pre[maxn], suf[maxn];
vector <int> q, a;

int main() {
    cin >> n;
    q.push_back(0);
    a.push_back(0);

    for (int i = 1, tmp; i <= n + 1; i++) {
        cin >> tmp;
        q.push_back(tmp);
        a.push_back(tmp);
    }

    sort(a.begin(), a.end());

    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    sort(b + 1, b + n + 1);

    for (int i = 1; i <= n; i++) {
        pre[i] = max(pre[i - 1], a[i] - b[i]);
        suf[n + 2 - i] = max(suf[n + 3 - i], a[n + 2 - i] - b[n + 1 - i]);
    }

    for (int i = 1; i <= n + 1; i++) {
        int tmp = (lower_bound(a.begin(), a.end(), q[i]) - a.begin());
        cout << max(pre[tmp - 1], suf[tmp + 1]) << " ";
    }
}