Submission #220653

#	Time	Username	Problem	Language	Result	Execution time	Memory
220653		srvlt	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	128 ms	10872 KiB

ho_t1

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

void dout() { cerr << '\n'; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << " " << H;
    dout(T...);
}

#ifdef LOCAL
    #define dbg(...) cerr << #__VA_ARGS__, dout(__VA_ARGS__)
#else
    #define dbg(...) ;
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 2e5 + 123;
int n, a[N], b[N], suf[N], ans[N];

pii A[N];

int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif

    cin >> n;
    for (int i = 1; i <= n + 1; i++) {
        cin >> a[i];
        A[i] = {a[i], i};
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    sort(b + 1, b + n + 1);
    sort(A + 1, A + n + 2);
    suf[n + 2] = 0;
    for (int i = n + 1; i >= 2; i--) {
        suf[i] = max(suf[i + 1], A[i].fi - b[i - 1]);
    }
    int pref = 0;
    for (int i = 1; i <= n + 1; i++) {
        ans[A[i].se] = max(pref, suf[i + 1]);
        if (i == n + 1) {
            break;
        }
        pref = max(pref, A[i].fi - b[i]);
    }
    for (int i = 1; i <= n + 1; i++) {
        cout << ans[i] << ' ';
    }
}

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