Submission #763070

#	Time	Username	Problem	Language	Result	Execution time	Memory
763070		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	88 ms	13572 KiB

ho_t1

#ifdef MINHDEPTRAI

#include "/Library/Developer/CommandLineTools/usr/include/c++/v1/bits/stdc++.h"  
#include <chrono>
#define __gcd(a, b) gcd(a, b)
using namespace std ::chrono;
#else 
#include <bits/stdc++.h>
#endif

using namespace std;
#define foru(i, a, b) for(int i = a; i <= b; ++i)
#define ford(i, a, b) for(int i = a; i >= b; --i)
#define IOS ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp(a, b) make_pair(a, b)
#define endl '\n'

#define int long long
const int maxN = 2e6 + 5;
const int mod = 998244353;
const long long inf = 1e17;
int n, arr[maxN], b[maxN], ans[maxN], suffix[maxN], prefix[maxN];
pair<int, int> number[maxN];
bool used[maxN];
bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first) return a.second < b.second;

    return a.first < b.first;
}
signed main(){
    // freopen("input.txt", "r", stdin);
    // freopen("output1.txt", "w", stdout);
    // input
    IOS

    cin >> n;
    foru(i, 1, n + 1) {
        cin >> arr[i];
        number[i] = mp(arr[i], i);
    }

    foru(i, 1, n){
        cin >> b[i];
    }

    sort(number + 1, number + 2 + n);
    sort(b + 1, b + 1 + n);

    prefix[0] = 0;
    foru(i, 1, n){
        prefix[i] = max( prefix[i - 1],  max(number[i].first - b[i], 0ll)); 
    }

    suffix[n + 1] = 0;
    ford(i, n, 1){
        suffix[i] = max(suffix[i + 1], max(number[i + 1].first - b[i], 0ll));
    }

    foru(i, 1, n + 1){
        ans[number[i].second] = max({prefix[i - 1], suffix[i], 0ll});
    }

    foru(i, 1, n + 1) cout << ans[i] << " ";
}

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