Submission #506157

#	Time	Username	Problem	Language	Result	Execution time	Memory
506157		thomas_li	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	258 ms	23240 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],org[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];
		org[i] = a[i];
	}
	for(int i = 1; i <= n; i++){
		cin >> b[i];
	}
	sort(b+1,b+1+n); sort(a+1,a+2+n);
	for(int i = 1; i <= n+1; i++){
		pos[a[i]] = i;
	}
	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++){
		int p = pos[org[i]];	
		cout << max(pref[p-1],suff[p+1]) << " \n"[i==n+1];
	}

}

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