제출 #977729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977729		UltraFalcon	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	96 ms	19136 KiB

ho_t1

#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt")
#endif

#include <bits/stdc++.h>
#define int long long
using ll = long long;

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;

    vector<int> a(n+1);
    for (auto &x : a) cin >> x;

    vector<int> b(n);
    for (auto &x : b) cin >> x;

    vector<int> sorted_b(b);
    sort(sorted_b.begin(), sorted_b.end());

    vector<pair<int, int>> sorted_idx;
    for (int i=0; i<=n; i++) {
        sorted_idx.push_back({a[i], i});
    }
    sort(sorted_idx.begin(), sorted_idx.end());

    vector<int> pref(n+2, 0);
    for (int i=0; i<n; i++) {
        pref[i+1] = max(pref[i], max(sorted_idx[i].first - sorted_b[i], 0LL));
    }
    vector<int> suff(n+2, 0);
    for (int i=n; i>0; i--) {
        suff[n-i+1] = max(suff[n-i], max(sorted_idx[i].first - sorted_b[i-1], 0LL));
    }

    vector<int> res(n+1, -1);
    for (int i=0; i<=n; i++) {
        res[sorted_idx[i].second] = max(pref[i], suff[n-i]);
    }

    for (auto &x : res) {
        cout << x << " "; 
    }
    cout << "\n";

}

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