Submission #503990

#	Time	Username	Problem	Language	Result	Execution time	Memory
503990		sidon	Road Construction (JOI21_road_construction)	C++17	12 / 100	5257 ms	79776 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
 
#define C(Z) lower_bound(xVals, xVals + N, Z) - xVals
#define calc(i, j) max(abs(X[i] - X[j]), abs(Y[i] - Y[j]))
#define int int64_t

const int LIM = 250'000;

int N, K, ext;
int X[LIM], Y[LIM], byY[LIM], xVals[LIM], xPos[LIM];
map<int, int> done[LIM];

bool build(int dist, bool final) {
	set<array<int, 2>> on;
	for(int i = 0; i < N; ++i)
		done[i].clear();

	int p = 0, f = 0;
 
 	for(int _ = 0; _ < N; ++_) {
 		int i = byY[_];
		while(Y[i] - Y[byY[p]] > dist)
			on.erase({X[byY[p]], byY[p]}), ++p;
 
		auto j = on.lower_bound({(X[i] - dist), -1});
		bool nxt = 1;
 
		while(j != end(on) && (*j)[0] <= X[i] + dist) {
			f += (++done[(*j)[1]][i] < 2);
			if(final && calc(i, (*j)[1]) == dist && !--ext) {
				--dist;
 
				while(Y[i] - Y[byY[p]] > dist)
					on.erase({X[byY[p]], byY[p]}), ++p;
 
				j = on.lower_bound({(X[i] - dist), -1});
				nxt = 0;
			}
			if(!final && f >= K) return 0;
			if(nxt) ++j;
			nxt = 1;
		}
 
		on.insert({X[i], i});
	}
	return f + 1;
}

 
int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
 
	cin >> N >> K;
 
	for(int i = 0, x, y; i < N; ++i) {
		cin >> x >> y;
		X[i] = x + y;
		Y[i] = x - y;
		byY[i] = i;
		xVals[i] = X[i];
	}

	sort(byY, byY + N, [&](int &i, int &j) {
		return Y[i] < Y[j];
	});
	sort(xVals, xVals + N);
 
	for(int i = 0; i < N; ++i)
		xPos[i] = C(X[i]);
 
	int dist = -1;

	for(int b = 1LL<<33, c; b /= 2; ) {
		if((c = build(dist + b, 0))) dist += b, ext = K - (c - 1);
	}
	++dist;
	build(dist, 1);

	int res[K], p = 0;	
	for(int i = 0; i < N; ++i)
		for(auto [j, _] : done[i])
			res[p++] = calc(i, j);

	sort(res, res + K);
	for(int i : res) cout << i << '\n';
}

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