Submission #440752

#	Time	Username	Problem	Language	Result	Execution time	Memory
440752		idontreallyknow	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	151 ms	12524 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define SZ(x) ((int)((x).size()))
#define debug(x) cerr << #x << " = " << x << '\n'
const int mx = 2e5+50;
int a[mx], b[mx], c[mx], pref[mx], suff[mx], ord[mx];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<pii> stuff;
    for (int q = 1; q <= n+1; q++) {
        cin >> a[q];
        stuff.emplace_back(a[q],q);
        c[q] = a[q];
    }
    sort(c+1,c+n+2);
    sort(stuff.begin(), stuff.end());
    for (int q = 0; q < SZ(stuff); q++) ord[stuff[q].se] = q+1;
    for (int q = 1; q <= n; q++) cin >> b[q];
    sort(b+1,b+n+1);
    for (int q = 1; q <= n; q++) pref[q] = max(pref[q-1], max(0,c[q]-b[q]));
    for (int q = n+1; q >= 2; q--) suff[q] = max(suff[q+1], max(0,c[q]-b[q-1]));
    for (int q = 1; q <= n+1; q++) {
        cout << max(pref[ord[q]-1], suff[ord[q]+1]) << ' ';
    }
    cout << '\n';
    return 0;
}

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