Submission #1288847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288847		tunademayo	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	287 ms	14716 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define fi first
#define se second

const bool Multitest = 0;

const int N = 2e5 + 10;

int n, b[N + 1], dp[N];
pair<int, int> a[N];


void work()
{
	cin >> n;
	
	for(int i = 1 ; i <= n + 1 ; i++) cin >> a[i].fi, a[i].se = i;
	for(int i = 1 ; i <= n ; i++) cin >> b[i];
	sort(b + 1, b + 1 + n);
	sort(a + 1, a + 2 + n);
	
	multiset<int> s;
	
//	for(int i = 1 ; i <= n + 1 ; i++)
//	{
//		cout << a[i].fi << ' ' << a[i].se << '\n';
//	}
	
	for(int i = 2 ; i <= n + 1 ; i++) s.insert(a[i].fi - b[i - 1]);
	dp[a[1].se] = *s.rbegin(); //cout << *s.rbegin() << '\n';
	
	for(int i = 2 ; i <= n + 1 ; i++)
	{
		s.erase(s.find(a[i].fi - b[i - 1]));
		s.insert(a[i - 1].fi - b[i - 1]);
		
		dp[a[i].se] = *s.rbegin();
		
//		cout << i << ' ' << *s.rbegin() << '\n';
	}
	
	for(int i = 1 ; i <= n + 1 ; i++) cout << max(0, dp[i]) << ' ';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	
	int q = 1;
	
	if(Multitest)	cin >> q;
	
	while(q--) work();
}

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