Submission #371277

#	Time	Username	Problem	Language	Result	Execution time	Memory
371277		sam571128	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	130 ms	15708 KiB

ho_t1

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5+5;
int pref[N], suff[N];

signed main(){
	fastio
	int n;
	cin >> n;
	vector<pair<int,int>> v;
	int ans[n+1] = {};
	for(int i = 0;i < n+1;i++){
		int tmp;
		cin >> tmp;
		v.push_back({tmp,i});
	}
	sort(v.begin(),v.end());
	int arr[n];
	for(auto &x : arr) cin >> x;
	sort(arr,arr+n);
	for(int i = 0;i < n;i++){
		pref[i] = max(v[i].first-arr[i],(int)0);
		if(i!=0) pref[i] = max(pref[i],pref[i-1]);  
	}
	for(int i = n-1;~i;i--){
		suff[i] = max(v[i+1].first-arr[i],(int)0);
		if(i!=n-1) suff[i] = max(suff[i],suff[i+1]);
	}
	for(int i = 0;i <= n;i++){
		ans[v[i].second] = max((i==0 ? (int)0 : pref[i-1]),suff[i]);
	}
	for(auto x : ans) cout << x << " ";
}

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