Submission #1325554

#TimeUsernameProblemLanguageResultExecution timeMemory
1325554JuanJLJust Long Neckties (JOI20_ho_t1)C++20
100 / 100
167 ms13296 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i=  a; i<b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
using namespace std;
typedef long long ll;
int main(){
	ll n; cin>>n;
	vector<pair<ll,ll>> a(n+1); forn(i,0,n+1) cin>>a[i].fst, a[i].snd=i;
	vector<pair<ll,ll>> b(n); forn(i,0,n) cin>>b[i].fst , b[i].snd=i;

	sort(ALL(a));
	sort(ALL(b));	

	vector<ll> pm(n); 
	forn(i,0,n){ 
		pm[i]=max((ll)0,a[i].fst-b[i].fst);
		if(i>0) pm[i]=max(pm[i],pm[i-1]);

		//cout<<"("<<a[i].fst<<" "<<b[i].fst<<")"<<pm[i]<<" ";
	}//cout<<'\n';
	 
	vector<ll> sm(n); 
	for(int i = n-1; i>=0; i--){
		sm[i]=max((ll)0,a[i+1].fst-b[i].fst);
		if(i<n-1) sm[i]=max(sm[i],sm[i+1]);
	}

	//forn(i,0,n) cout<<"("<<a[i+1].fst<<" "<<b[i].fst<<")"<<sm[i]<<" "; cout<<'\n';

	vector<ll> res(n+1);
	res[a[0].snd]=sm[0];
	forn(i,0,n-1) res[a[i+1].snd]=max(pm[i],sm[i+1]);
	res[a[n].snd]=pm[n-1];

	for(auto i:res) cout<<i<<" "; cout<<'\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...