Submission #1250017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250017		gry3125	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	178 ms	12564 KiB

ho_t1

#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
using namespace std;

vector<ll> t;
void upd(int v, int tl, int tr, int pos, ll val) {
	if (tl == tr) {t[v] = val; return;}
	int tm = (tl + tr) / 2;
	if (pos <= tm) upd(2*v, tl, tm, pos, val);
	else upd(2*v+1, tm+1, tr, pos, val);
	t[v] = max(t[2*v], t[2*v+1]);
}
ll qry(int v, int tl, int tr, int l, int r) {
	if (l > r) return 0;
	if (l == tl && r == tr) return t[v];
	int tm = (tl + tr) / 2;
	ll lf = qry(2*v, tl, tm, l, min(tm, r));
	ll rg = qry(2*v+1, tm+1, tr, max(l, tm+1), r);
	return max(lf, rg);
}

int main() {
	int n; cin >> n; t.resize((1LL<<19));
	vector<pair<ll,int>> a(n+1);
	vector<ll> b(n), ans(n+1);
	for (int i = 0; i < n+1; i++) {
		cin >> a[i].fi; a[i].se = i;
	}
	for (int i = 0; i < n; i++) cin >> b[i];
	sort(all(a)); sort(all(b));
	for (int i = 0; i < n; i++) {
		upd(1, 1, (1LL<<18), i+1, a[i].fi-b[i]);
	}
	ans[a[n].se] = qry(1, 1, (1LL<<18), 1, (1LL<<18));
	for (int i = n-1; i >= 0; i--) {
		upd(1, 1, (1LL<<18), i+1, a[i+1].fi-b[i]);
		ans[a[i].se] = qry(1, 1, (1LL<<18), 1, (1LL<<18));
	}
	for (int i = 0; i < n+1; i++) {
		cout << max(0LL, ans[i]) << " ";
	}
	return 0;
}

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