Submission #971138

#	Time	Username	Problem	Language	Result	Execution time	Memory
971138		Roumak77	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	86 ms	15436 KiB

ho_t1

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

using ll = long long;

void solve(){
    ll n;
    cin >> n;

    vector<pair<ll, ll>> list_a(n + 1, pair<ll, ll>{0, 0});
    vector<ll> list_b(n, 0);

    vector<ll> proper_min(n + 1, 0);
    vector<ll> improper_min(n + 1, 0);

    for(ll i = 0; i <= n; i++){
        cin >> list_a[i].first;
        list_a[i].second = i;

    }

    for(ll i = 0; i < n; i++){
        cin >> list_b[i];
    }


    sort(list_a.begin(), list_a.end());
    sort(list_b.begin(), list_b.end());



    for(ll i = 0; i < n; i++){
        proper_min[i + 1] = max(proper_min[i], max((ll)0, list_a[i].first - list_b[i]));
    }

    for(ll i = n - 1; i >= 0; i--){
        improper_min[n - i] = max(improper_min[n - i - 1], max((ll)0, list_a[i + 1].first - list_b[i]));
    }


    vector<ll> ans(n + 1, 0);

    for(ll i = 0; i <= n; i++){
        ans[list_a[i].second] = max(proper_min[i], improper_min[n - i]);
    }

    for(ll i = 0; i <= n; i++){
        cout << ans[i] << " ";
    }





}


int main(){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;

    while(t--){
        solve();
    }
}

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