Submission #917835

#	Time	Username	Problem	Language	Result	Execution time	Memory
917835		oblantis	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	169 ms	18772 KiB

ho_t1

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 2e5 + 1;

void solve() {
	int n;
	cin >> n;
	pii a[n + 1];
	int out[n + 1], b[n];
	for(int i = 0; i <= n; i++){
		cin >> a[i].ff;
		a[i].ss = i;
	}
	multiset<int> s;
	sort(a, a + n + 1);
	for(int i = 0; i < n; i++){
		cin >> b[i];
	}
	sort(b, b + n);
	for(int i = 0; i < n; i++)s.insert(a[i].ff - b[i]);
	for(int i = n; i >= 0; i--){
		out[a[i].ss] = *s.rbegin();
		if(!i)continue;
		s.erase(a[i - 1].ff - b[i - 1]);
		s.insert(a[i].ff - b[i - 1]);
	}
	for(auto i : out)cout << max(0, i) << ' ';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

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