Submission #384279

#	Time	Username	Problem	Language	Result	Execution time	Memory
384279		sumit_kk10	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	121 ms	13332 KiB

ho_t1

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;

void solve(){
	int n;
	cin >> n;
	pair<int, int> a[n + 1], b[n];
	for(int i = 0; i <= n; ++i){
		cin >> a[i].first;
		a[i].second = i;
	}
	for(int i = 0; i < n; ++i){
		cin >> b[i].first;
		b[i].second = i;
	}
	sort(a, a + n + 1);
	sort(b, b + n);
	// now for each i in a it is removed then we take a[i] - b[i]. :hmm:
	int ans[n + 1][2];
	for(int i = 0; i < n; ++i){
		ans[i][0] = max(a[i].first - b[i].first, 0);
		ans[i][1] = max(a[i + 1].first - b[i].first, 0);
	}
	ans[n][1] = 0;
	ans[n][0] = 0;
	int pre_mx[n + 1] = {0}, suf_mx[n + 1] = {0};
	pre_mx[0] = ans[0][0];
	for(int i = 1; i <= n; ++i)
		pre_mx[i] = max(pre_mx[i - 1], ans[i][0]);
	suf_mx[n] = 0;
	suf_mx[n - 1] = ans[n - 1][1];
	for(int i = n - 2; i >= 0; --i)
		suf_mx[i] = max(suf_mx[i + 1], ans[i][1]);
	vector<int> res(n + 1);
	for(int i = 0; i <= n; ++i){
		int idx = a[i].second;
		if(i != 0)
			res[idx] = max(pre_mx[i - 1], suf_mx[i]);
		else
			res[idx] = suf_mx[i];
		// cout << ans[i][1] << ' ';
	}
	// cout << endl;
	for(auto k : res)
		cout << k << ' ';
	cout << "\n";
}

int main(){
    fast;
	int t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

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