Submission #1122683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122683		SulA	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	88 ms	6984 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC target("popcnt")
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define popcount __builtin_popcountll

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n; cin >> n;
    pair<int,int> a[n+1];
    int b[n];
    for (int i = 0; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    for (int& x : b) cin >> x;
    sort(a, a+n+1);
    sort(b, b+n);
    int pref[n], suff[n], ans[n+1]{};
    pref[0] = max(0, a[0].first - b[0]);
    for (int i = 1; i < n; i++) {
        pref[i] = max(pref[i-1], a[i].first - b[i]);
    }
    suff[n-1] = max(0, a[n].first - b[n-1]);
    for (int i = n-2; i >= 0; i--) {
        suff[i] = max(suff[i+1], a[i+1].first - b[i]);
    }
    for (int i = 0; i <= n; i++) {
        int ind = a[i].second;
        if (i != 0) ans[ind] = max(ans[ind], pref[i-1]);
        if (i < n) ans[ind] = max(ans[ind], suff[i]);
    }
    for (int x : ans) cout << x << " ";

}

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