Submission #639826

#TimeUsernameProblemLanguageResultExecution timeMemory
639826danikoynovJust Long Neckties (JOI20_ho_t1)C++14
100 / 100
397 ms19360 KiB
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;

struct element
{
    int x, idx;

    element(int _x = 0, int _idx = 0)
    {
        x = _x;
        idx = _idx;
    }

    bool operator < (const element &e) const
    {
        return x < e.x;
    }
} e[maxn];

int n, a[maxn], b[maxn], ans[maxn];

void solve()
{
    cin >> n;
    n ++;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        e[i] = element(a[i], i);
    }

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

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

    sort(b + 1, b + n);

    multiset < int > st;
    for (int i = 1; i < n; i ++)
        st.insert(max(0, e[i + 1].x - b[i]));

    for (int i = 1; i <= n; i ++)
    {
        ans[e[i].idx] = *st.rbegin();
        ///cout << "fine " << e[i].idx << endl;
        if (i != n)
        {
            st.erase(st.find(max(0, e[i + 1].x - b[i])));
            ///cout << e[i + 1].x - b[i] << " " << e[i].x - b[i] << endl;
            st.insert(max(0, e[i].x - b[i]));

        }
    }

    for (int i = 1; i <= n; i ++)
        cout << ans[i] << " ";

    cout << endl;

}
int main()
{
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...