Submission #643661

#	Time	Username	Problem	Language	Result	Execution time	Memory
643661		Juan	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	410 ms	18656 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int ppl[maxn], ans[maxn];
multiset<int> st;
pair<int, int> ties[maxn];

int main(){
	int n; cin >> n;
	for(int i = 0; i <= n; i++) cin >> ties[i].first;
	for(int i = 0; i < n; i++) cin >> ppl[i];
	for(int i = 0; i <= n; i++) ties[i].second = i;
	sort(ppl, ppl+n);
	sort(ties, ties+n+1);
	for(int i = 1; i <= n; i++) st.insert(ties[i].first-ppl[i-1]);
	// ans[tie[0].second] = st.rbegin();
	ans[ties[0].second] = max(0, *st.rbegin());
	for(int i = 0; i < n; i++){
		int id = ties[i+1].second;
		// cout << i << " " << id << "\n";
		st.insert(ties[i].first-ppl[i]);
		st.erase(st.find(ties[i+1].first-ppl[i]));
		ans[id] = max(0, *st.rbegin());
	}

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

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