Submission #1235229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235229		k1r1t0	Road Construction (JOI21_road_construction)	C++20	100 / 100	1524 ms	18224 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 251000;

int n, k;
array<int, 2> pt[N];
vector<array<int, 2>> tt;

int get(int i, int j) {
	return max(abs(pt[i][0] - pt[j][0]), abs(pt[i][1] - pt[j][1]));
}

void solve(int dist) {
	tt.clear();
	if (dist < 1) return;
	set<array<int, 2>> st;
	int ptr = 1;
	for (int i = 1; i <= n && (int) tt.size() < k; i++) {
		auto [x, y] = pt[i];
		while (pt[ptr][0] < x - dist) {
			st.erase({pt[ptr][1], ptr});
			ptr++;
		}
		auto it = st.lower_bound({y - dist, 1});
		while ((int) tt.size() < k && it != st.end() && (*it)[0] <= y + dist) {
			tt.push_back({i, (*it)[1]});
			it++;
		}
		st.insert({y, i});
	}
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> pt[i][0] >> pt[i][1];
	for (int i = 1; i <= n; i++) {
		auto [x, y] = pt[i];
		pt[i][0] = x + y;
		pt[i][1] = x - y;
	}
	sort(pt + 1, pt + 1 + n);
	int l = 1, r = (int)(4e9);
	while (l < r) {
		int mid = (l + r) / 2;
		solve(mid);
		assert((int) tt.size() <= k);
		if ((int) tt.size() == k) r = mid;
		else l = mid + 1;
	}
	solve(l - 1);
	vector<array<int, 2>> cc = tt;
	assert((int) cc.size() < k);
	solve(l);
	assert((int) tt.size() == k);
	for (int i = 0; i < k && (int) cc.size() < k; i++)
		if (get(tt[i][0], tt[i][1]) == l)
			cc.push_back(tt[i]);
	assert((int) cc.size() == k);
	sort(begin(cc), end(cc), [&](auto a, auto b) {
		return get(a[0], a[1]) < get(b[0], b[1]);
	});
	for (int i = 0; i < k; i++)
		cout << get(cc[i][0], cc[i][1]) << '\n';
}

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