Submission #1124556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124556		Error42	Road Construction (JOI21_road_construction)	C++20	100 / 100	1985 ms	10252 KiB

road_construction

#include <algorithm>
#include <climits>
#include <compare>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

using ll = long long;

ll const INF = LLONG_MAX / 3;

struct point {
	ll x, y;

	auto operator <=>(point const& rhs) const = default;

	point swapped() const {
		return { y, x };
	}

	ll dist(point const& rhs) const {
		return max(abs(x - rhs.x), abs(y - rhs.y));
	}
};

vector<ll> attempt(vector<point> const& cities, ll const dist, ll const k) {
	set<point> possible;

	ll i = 0;

	vector<ll> ret;

	for (ll j = 0; j < cities.size(); j++) {
		while (cities[j].x - cities[i].x > dist) {
			possible.erase(cities[i].swapped());
			i++;
		}

		auto const lo = possible.lower_bound({ cities[j].y - dist, -INF });
		auto const hi = possible.lower_bound({ cities[j].y + dist, INF });

		for (auto it = lo; it != hi; ++it) {
			ret.push_back(cities[j].swapped().dist(*it));

			if (ret.size() == k)
				return ret;
		}

		possible.insert(cities[j].swapped());
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n, k;
	cin >> n >> k;

	vector<point> cities(n);
	for (point& p : cities) {
		ll x, y;
		cin >> x >> y;

		p = { x + y, x - y };
	}

	sort(cities.begin(), cities.end());

	ll lo = 0;
	ll hi = 4'000'000'010;

	while (lo + 1 != hi) {
		ll const mid = (lo + hi) / 2;

		auto const result = attempt(cities, mid, k);

		if (result.size() >= k)
			hi = mid;
		else
			lo = mid;
	}

	auto ans = attempt(cities, lo, k);
	sort(ans.begin(), ans.end());
	ans.resize(k, lo + 1);

	for (ll const& x : ans)
		cout << x << "\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