Submission #201321

#	Time	Username	Problem	Language	Result	Execution time	Memory
201321		parsa_mobed	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	524 ms	14840 KiB

ho_t1

#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;
}

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