Submission #575070

#	Time	Username	Problem	Language	Result	Execution time	Memory
575070		pokmui9909	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	133 ms	15504 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N;
pair<ll, ll> A[200005];
ll B[200005], R[200005];
ll P[200005], S[200005];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N;
    for(ll i = 1; i <= N + 1; i++){
        cin >> A[i].first;
        A[i].second = i;
    }
    for(ll i = 1; i <= N; i++){
        cin >> B[i];
    }
    sort(A + 1, A + N + 2);
    sort(B + 1, B + N + 1);
    for(ll i = 1; i <= N; i++){
        P[i] = max(P[i - 1], A[i].first - B[i]);
    }
    for(ll i = N; i >= 1; i--){
        S[i] = max(S[i + 1], A[i + 1].first - B[i]);
    }
    for(ll i = 1; i <= N + 1; i++){
        R[A[i].second] = max(P[i - 1], S[i]);
    }
    for(ll i = 1; i <= N + 1; i++){
        cout << R[i] << ' ';
    }
}

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