Submission #554905

#	Time	Username	Problem	Language	Result	Execution time	Memory
554905		endy	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	140 ms	20092 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

int n;
vector <long long int > b;
vector < pair<long long int, int> > a;
vector <long long int> dif1;
vector <long long int> dif2;
long long int max1, max2;
vector < pair<int, long long int>> c;

int main(){
	
	//freopen("in.in", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n;

	for(int i=0 ; i<=n ; i++){

		long long int x;
		cin >> x;

		a.push_back(make_pair(x, i));
	}

	for(int i=0 ; i<n ; i++){

		long long int x;
		cin >> x;

		b.push_back(x);
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	for(int i=0 ; i<n ; i++){

		long long int m;

		if(a[i].first < b[i]){
			m = 0;
		}else{
			m = a[i].first - b[i];
		}

		if(max1 < m) max1 = m;

		dif1.push_back(max1);

	}


	for(int i=n-1 ; i>=0 ; i--){

		long long int m;

		if(a[i+1].first < b[i]){
			m = 0;
		}else{
			m = a[i+1].first - b[i];
		}

		if(max2 < m) max2 = m;

		dif2.push_back(max2);
	}



	int cont=0;

	while(cont <= n){

		int k;

		if(cont == 0){
			k = dif2[n-cont-1];
		}else if(cont == n){
			k = dif1[cont-1];
		}else{

			k = max(dif1[cont-1], dif2[n-cont-1]);
		}

		c.push_back(make_pair(a[cont].second, k));

		cont++;
	}

	sort(c.begin(), c.end());

	for(int i=0 ; i<=n ; i++){

		cout << c[i].second << " ";
	}

	return 0;
}

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