Submission #221870

#	Time	Username	Problem	Language	Result	Execution time	Memory
221870		davooddkareshki	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	319 ms	20440 KiB

ho_t1

#include<bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define int long long

const int maxn = 5e5+10;

int a[maxn], b[maxn], pr[maxn], sf[maxn], n;
vector<pair<int,int>> A, B;
int ans[maxn];

signed main()
{
    cin>> n;
    for(int i = 1; i <= n+1; i++)
    {
        cin>> a[i];
        A.push_back({a[i],i});
    }
    for(int i = 1; i <= n; i++)
    {
        cin>> b[i];
        B.push_back({b[i],i});
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for(int i = 1; i <= n; i++)
        pr[i] = max(pr[i-1], A[i-1].F-B[i-1].F);
    for(int i = n+1; i >= 2; i--)
        sf[i] = max(sf[i+1], A[i-1].F-B[i-2].F);

    for(int i = 1; i <= n+1; i++)
        ans[A[i-1].S] = max(sf[i+1], pr[i-1]);
    for(int i = 1; i <= n+1; i++)
        cout<< ans[i] <<" ";
}

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