Submission #201321

#TimeUsernameProblemLanguageResultExecution timeMemory
201321parsa_mobedJust Long Neckties (JOI20_ho_t1)C++14
100 / 100
524 ms14840 KiB
#include <bits/stdc++.h>

using namespace std;
#define pii pair <int , int>
#define F first
#define S second
const int N = 2e5 + 10;
int a[N], b[N], p[N], ans[N];

bool cmp(int i, int j) {return a[i] < a[j];}

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n + 1; i++) cin >> a[i], p[i] = i;
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(b + 1, b + n + 1);
    sort(p + 1, p + n + 2, cmp);
    set <pii> st;
    for (int i = 1; i <= n; i++) st.insert({-1*max(a[p[i]] - b[i], 0), i});
    ans[p[n+1]] = (*st.begin()).F;
    for (int i = n + 1; i >= 2; i--) {
        st.erase({-1*max(a[p[i - 1]] - b[i - 1], 0), i-1});
        st.insert({-1*max(a[p[i]] - b[i - 1], 0), i-1});
        ans[p[i - 1]] = (*st.begin()).F;
    }
    for (int i = 1; i <= n + 1; i++) cout << -1*ans[i] << " ";
    cout << "\n";


    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...