Submission #1326486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326486		joacru	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	66 ms	7120 KiB

ho_t1

#include <bits/stdc++.h>

#define forn(i,n) for(int i=0;i<int(n);++i)
#define fort(i,n) for(int i=0;i<=int(n);++i)
#define fori(i,a,n) for(int i=a;i<int(n);++i)
#define forit(i,a,n) for(int i=a;i<=int(n);++i)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()

#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)

#define LINE cerr<<"===================================="<<endl

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
	os<<"[";
	forn(i,v.size()){
		if(i) os<<" ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

typedef long long ll;
typedef long double ld;

void solve(){
	
	int n;
	cin>>n;
	
	vector<pair<int,int>> a(n+1);
	vector<int> b(n);
	forn(i,n+1){
		cin>>a[i].first;
		a[i].second = i;
	}
	for(int &x: b) cin>>x;

	sort(ALL(a));
	sort(ALL(b));
	
	vector<int> fromLeft(n+1);
	forn(i,n){
		fromLeft[i+1] = fromLeft[i];
		int s = max(a[i].first - b[i], 0);
		//~ DBG3(a[i].first, a[i].second, b[i]);
		fromLeft[i+1] = max(fromLeft[i+1], s);
	}
	
	vector<int> fromRight(n+1);
	for(int i=n-1;i>=0;--i){
		fromRight[i] = fromRight[i+1];
		int s = max(a[i+1].first - b[i], 0);
		fromRight[i] = max(fromRight[i], s);
	}
	
	//~ DBG(fromLeft);
	//~ DBG(fromRight);
	
	vector<int> ans(n + 1);
	
	forn(i,n+1){
		int aux = max(fromLeft[i], fromRight[i]);
		ans[a[i].second] = aux;
	}
	
	for(int x: ans) cout<<x<<" ";
	cout<<"\n";
	
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
		assert(freopen("input.in", "r", stdin));
		//~ freopen("output.out", "w", stdout);
	#endif
	
	#ifdef LOCAL
	int tcs; cin>>tcs;
	while(tcs--)
	#endif
	solve();

	return 0;
}

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