Submission #1281431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281431		shirokito	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	196 ms	14788 KiB

ho_t1

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

using ll = long long;

const int N = 2e5 + 24;

struct Data {
	int v, i;
	bool operator < (Data &oth) { return v < oth.v; }
} a[N];

int n, b[N], ans[N];

void solve() {
	cin >> n;
	for (int i = 1; i <= n + 1; i++) {
		cin >> a[i].v;
		a[i].i = i;
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}

	sort(a + 1, a + n + 2);
	sort(b + 1, b + n + 1);

	multiset<int> s;
	for (int i = 1; i <= n; i++) {
		s.insert({a[i].v - b[i]});
	}

	ans[a[n + 1].i] = *s.rbegin();

	for (int i = n; i >= 1; i--) {
		s.erase(s.find({a[i].v - b[i]}));
		s.insert({a[i + 1].v - b[i]});
		ans[a[i].i] = *s.rbegin();
	}

	for (int i = 1; i <= n + 1; i++) {
		cout << ans[i] << " \n" [i == n + 1];
	}
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);

	int T = 1; // cin >> T;
	while (T--) {
		solve();
	}
}

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