Submission #994549

#	Time	Username	Problem	Language	Result	Execution time	Memory
994549		mnieplowicz	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	84 ms	12428 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;

pair<int, int> A[200005];
int B[200005];
int M1[200005];
int M2[200005];
int pref[200005];
int suf[200005];
int res[200005];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	for(int i = 0; i <= n; i++){
		cin >> A[i].first;
		A[i].second = i;
	}
	for(int i = 0; i < n; i++) cin >> B[i];
	sort(B, B+n);
	sort(A, A+n+1);
	for(int i = 0; i < n; i++) {
		M1[i] = max(0, A[i].first - B[i]);
		M2[i] = max(0, A[i+1].first - B[i]);
		//cout << M1[i] << " " << M2[i] << '\n';
	}
	pref[0] = M1[0];
	for(int i = 1; i < n; i++) {
		pref[i] = max(pref[i-1], M1[i]);
		//cout << pref[i] << " ";
	}
	//cout << '\n';
	for(int i = n-1; i >= 0; i--) {
		suf[i] = max(suf[i+1], M2[i]);
		//cout << suf[i] << " ";
	}
	//cout << '\n';
	res[A[n].second] = pref[n-1];
	res[A[0].second] = suf[0];
	for(int i = 1; i < n; i++){
		res[A[i].second] = max(pref[i-1], suf[i]);
	}
	for(int i = 0; i <= n; i++) cout << res[i] << " ";
	
	return 0;
}

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