Submission #677564

#	Time	Username	Problem	Language	Result	Execution time	Memory
677564		Nahian9696	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	207 ms	23852 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

#define f0(i,n) for(int32_t i = 0; i <  (n); i++)
#define f1(i,n) for(int32_t i = 1; i <= (n); i++)

#define inp(n) lli n; cin >> n
#define inparr(arr,n) lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]

#define all(x) (x).begin(), (x).end()

int main () {
    inp(n);
    inparr(a, n+1);
    inparr(b, n);

    vector<pair<lli, lli>> arr, brr;
    f0(i, n+1) arr.push_back({a[i], i});
    f0(i, n) brr.push_back({b[i], i});

    sort(all(arr));
    sort(all(brr));

    lli prefmx[n], sufmx[n];
    prefmx[0] = max(arr[0].first-brr[0].first, 0ll);
    sufmx[n-1] = max(arr[n].first-brr[n-1].first, 0ll);

    for (int32_t i = 1; i < n; i++) {
        // prefmx[i] = max(prefmx[i-1], a[i]-b[i]);
        prefmx[i] = max(prefmx[i-1], arr[i].first-brr[i].first);
    }
    for (int32_t i = n-2; i >= 0; i--) {
        // sufmx[i] = max(sufmx[i+1], a[i+1]-b[i]);
        sufmx[i] = max(sufmx[i+1], arr[i+1].first-brr[i].first);
    }
    vector<lli> ans;
    // cout << sufmx[0] << " ";
    ans.push_back(sufmx[0]);
    f1(i, n-1) {
        // cout << max(prefmx[i-1], sufmx[i]) << " ";
        ans.push_back(max(prefmx[i-1], sufmx[i]));
    }
    // cout << prefmx[n-1] << endl;
    ans.push_back(prefmx[n-1]);

    lli ans2[n+1];
    f0(i, n+1) ans2[arr[i].second] = ans[i];

    f0(i, n+1) cout << ans2[i] << " ";
    cout << endl;

    
    return 0;


}

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