Submission #957240

#TimeUsernameProblemLanguageResultExecution timeMemory
957240aaron_dcoderJust Long Neckties (JOI20_ho_t1)C++17
100 / 100
189 ms15468 KiB
#define NDEBUG


#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;

int main()
{
	ll N;
	cin >> N;

	vector<pll> A(N+1);
	for (ll i = 0; i < N+1; ++i)
	{
		cin >> A[i].e0;
		A[i].e1=i;
	}

	vector<ll> B(N);
	for (ll i = 0; i < N; ++i)
	{
		cin >> B[i];
	}

	sort(A.begin(),A.end());
	sort(B.begin(),B.end());

	vector<ll> fcost(N);
	vector<ll> bcost(N+1,0);

	fcost[0] = A[0].e0-B[0];
	for (ll i = 1; i < N; ++i)
	{
		fcost[i] = max(fcost[i-1], A[i].e0-B[i]);
	}

	bcost[N-1] = A[N].e0-B[N-1];
	for (ll i = N-2; i >= 0; --i)
	{
		bcost[i] = max(bcost[i+1], A[i+1].e0-B[i]);
	}

	vector<ll> ans(N+1);

	ans[A[0].e1] = max(bcost[0],0ll);
	for (ll i = 0; i < N; ++i)
	{
		ans[A[i+1].e1] = max({fcost[i],bcost[i+1],0ll});
	}

	for (ll o : ans)
	{
		cout << o << " ";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...