Submission #506150

#	Time	Username	Problem	Language	Result	Execution time	Memory
506150		thomas_li	Just Long Neckties (JOI20_ho_t1)	C++17	9 / 100	193 ms	21816 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
const int MM = 2e5+5;
int n; long long pref[MM],suff[MM],c[MM],a[MM],b[MM];
map<int,int> pos;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n+1; i++){
		cin >> a[i];
		pos[a[i]] = i;
	}
	for(int i = 1; i <= n; i++){
		cin >> b[i];
	}
	sort(b+1,b+1+n); sort(a+1,a+2+n);
	pref[0] = -1e18;
	for(int i = 1; i <= n; i++){
		pref[i] = max(pref[i-1],max(0ll,a[i]-b[i]));
	}
	suff[n+2] = -1e18;
	for(int i = n+1; i >= 2; i--){
		suff[i] = max(suff[i+1],max(0ll,a[i]-b[n-(n+1-i)]));
	}
	for(int i = 1; i <= n+1; i++){
		c[pos[a[i]]] = max(pref[i-1],suff[i+1]);
	}
	for(int i = 1; i <= n+1; i++){
		cout << c[i] << " \n"[i==n+1];
	}
}

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