Submission #206199

#	Time	Username	Problem	Language	Result	Execution time	Memory
206199		combi1k1	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	137 ms	7032 KiB

ho_t1

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define X   first
#define Y   second

#define all(x)  x.begin(),x.end()
#define sz(x)   (int)x.size()

#define pb      emplace_back
#define endl    "\n"

const ll    inf = 1e18;
const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;

ii  a[N];
int b[N];

int Pre[N];
int Suf[N];
int ans[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    for(int i = 0 ; i <= n ; ++i)   {
        int x;  cin >> x;
        a[i].X = x;
        a[i].Y = i;
    }
    for(int i = 1 ; i <= n ; ++i)
        cin >> b[i];

    sort(a    ,a + 1 + n);
    sort(b + 1,b + 1 + n);

    for(int i = 1 ; i <= n ; ++i)   Pre[i] = max(Pre[i - 1],a[i - 1].X - b[i]);
    for(int i = n ; i >= 1 ; --i)   Suf[i] = max(Suf[i + 1],a[i].X - b[i]);

    for(int i = 0 ; i <= n ; ++i)
        ans[a[i].Y] = max(Pre[i],Suf[i + 1]);

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

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