Submission #625257

#	Time	Username	Problem	Language	Result	Execution time	Memory
625257		boris_mihov	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	119 ms	10836 KiB

ho_t1

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;

int n;
int a[MAXN];
int b[MAXN];
int idx[MAXN];
int output[MAXN];
int prefix[MAXN];
int suffix[MAXN];

void solve()
{
    std::iota(idx + 1, idx + 2 + n, 1);
    std::sort(idx + 1, idx + 2 + n, [&](int x, int y)
    {
        return a[x] < a[y];
    });

    std::sort(a + 1, a + 2 + n);
    std::sort(b + 1, b + 1 + n);
    
    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = std::max(prefix[i - 1], a[i] - b[i]);
    }

    for (int i = n ; i >= 1 ; --i)
    {
        suffix[i] = std::max(suffix[i + 1], a[i+1] - b[i]);
    }

    for (int i = 1 ; i <= n + 1 ; ++i)
    {
        output[idx[i]] = std::max(prefix[i - 1], suffix[i]);
    }

    for (int i = 1 ; i <= n + 1 ; ++i)
    {
        std::cout << output[i] << ' ';
    }

    std::cout << '\n';
}

void read()
{
    std::cin >> n;
    for (int i = 1 ; i <= n + 1 ; ++i) std::cin >> a[i];
    for (int i = 1 ; i <= n ; ++i) std::cin >> b[i];
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

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