Submission #387324

#	Time	Username	Problem	Language	Result	Execution time	Memory
387324		SeDunion	Road Construction (JOI21_road_construction)	C++17	100 / 100	4634 ms	21468 KiB

road_construction

#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 250000 + 6;

ll X[N], Y[N];

int p[N];
int n, k, x[N], y[N];
vector<ll>xs,ys;

int F[N];
void upd(int pos, int v) {
	while (pos < N) {
		F[pos] += v;
		pos |= pos + 1;
	}
}
int get(int pos) {
	int r = 0;
	while (pos >= 0) {
		r += F[pos];
		pos &= pos + 1, pos--;
	}
	return r;
}

bool check(ll M) {
	int res = 0;
	int l = 1;
	for (int i = 0 ; i < N ; ++ i) F[i] = 0;
	for (int i = 1 ; i <= n ; ++ i) {
		while (l < i && X[p[i]] - X[p[l]] >= M) {
			upd(y[p[l]], -1);
			l++;
		}
		int sx = lower_bound(ys.begin(), ys.end(), Y[p[i]] - M + 1) - ys.begin();
		int ex = upper_bound(ys.begin(), ys.end(), Y[p[i]] + M - 1) - ys.begin() - 1;
		res += get(ex) - get(sx - 1);
		if (res >= k) break;
		upd(y[p[i]], +1);
	}
	while (l <= n) upd(y[p[l]], -1), ++l;
	return res >= k;
}

vector<ll>ANS;

void restore(ll M) {
	set<pair<ll,ll>>S = {{Y[p[1]], X[p[1]]}};
	int l = 1;
	for (int i = 2 ; i <= n ; ++ i) {
		while (l < i && X[p[i]] - X[p[l]] >= M) {
			S.erase({Y[p[l]], X[p[l]]});
			l++;
		}
		auto st = S.lower_bound(pair{Y[p[i]] - M + 1, -1e10});
		for (; st != S.end() ; ++ st) {
			if (max(abs(st->first - Y[p[i]]), abs(st->second - X[p[i]])) < M) {
				ANS.emplace_back(max(abs(st->first - Y[p[i]]), abs(st->second - X[p[i]])));
			} else break;
		}
		S.insert({Y[p[i]], X[p[i]]});
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1 ; i <= n ; ++ i) {
		ll a, b;
		cin >> a >> b;
		X[i] = a + b, Y[i] = a - b;
		xs.emplace_back(X[i]), ys.emplace_back(Y[i]);
	}
	sort(xs.begin(), xs.end()); xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
	sort(ys.begin(), ys.end()); ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
	for (int i = 1 ; i <= n ; ++ i) {
		x[i] = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
		y[i] = lower_bound(ys.begin(), ys.end(), Y[i]) - ys.begin();
	}
	for (int i = 1 ; i <= n ; ++ i) {
		p[i] = i;
	}
	sort(p + 1, p + 1 + n, [](int i, int j) {
		return X[i] < X[j];
	});
	ll L = 1, R = ll(1e10);
	ll ans = -1;
	while (L <= R) {
		ll M = (L + R) / 2;
		int res = check(M);
		if (!res) { // ? < k
			ans = M;
			L = M + 1;
		} else {
			R = M - 1;
		}
	}
	assert(ans != -1);
	restore(ans);
	sort(ANS.begin(), ANS.end());
	for (ll i : ANS) cout << i << endl;;
	int cnt = ANS.size();
	for (; cnt < k ; ++cnt) {
		cout << ans << "\n";
	}
	cout << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35