Submission #520911

#	Time	Username	Problem	Language	Result	Execution time	Memory
520911		AdamGS	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	88 ms	15556 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
pair<ll,int>A[LIM];
ll B[LIM], pref[LIM], suf[LIM], ans[LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	rep(i, n+1) {
		cin >> A[i].st;
		A[i].nd=i;
	}
	rep(i, n) cin >> B[i];
	sort(A, A+n+1);
	sort(B, B+n);
	rep(i, n) {
		if(i) pref[i]=pref[i-1];
		pref[i]=max(pref[i], max(A[i].st-B[i], 0ll));
	}
	for(int i=n-1; i>=0; --i) {
		suf[i]=suf[i+1];
		suf[i]=max(suf[i], max(A[i+1].st-B[i], 0ll));
	}
	ans[A[0].nd]=suf[0];
	ans[A[n].nd]=pref[n-1];
	for(int i=1; i<n; ++i) {
		ans[A[i].nd]=max(pref[i-1], suf[i]);
	}
	rep(i, n+1) cout << ans[i] << " ";
	cout << '\n';
}

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