Submission #1139060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139060		Math4Life2020	Road Construction (JOI21_road_construction)	C++20	6 / 100	2793 ms	14316 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

ll N,K; const ll INF = 1e18;
vector<pii> vtwn;
vector<ll> dlog; //distance log

set<pii> s0; //set of currently active
//{y,x}

bool test(ll D0) { //if >=K roads with distance <=D0 -> return 1
	dlog.clear();
	s0.clear();
	for (pii pt: vtwn) {
		if (dlog.size()>=K) {
			return 1;
		}
		ll x = pt.first; ll y = pt.second;
		vector<pii> vdel; //vector to delete
		auto A0 = s0.lower_bound({y-D0,-INF});
		while (A0!=s0.end() && ((*A0).first<=y+D0) && dlog.size()<K) {
			pii p0 = *A0;
			ll y0 = p0.first; ll x0 = p0.second;
			ll d0 = llabs(y-y0)+llabs(x-x0);
			if (d0<=D0) {
				dlog.push_back(d0);
			}
			if ((x-x0)>D0) {
				vdel.push_back(p0);
			}
			A0++;
		}
		for (pii p0: vdel) {
			s0.erase(p0);
		}
		s0.insert({y,x});
	}
	return (dlog.size()>=K);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N >> K;
	for (ll i=0;i<N;i++) {
		ll x,y; cin >> x >> y;
		vtwn.push_back({x,y});
	}
	sort(vtwn.begin(),vtwn.end());
	ll Dmin = 0;
	ll Dmax = 2e9+5;
	while (Dmin != Dmax) {
		ll Dt = (Dmin+Dmax+1)/2;
		if (test(Dt)) {
			Dmax = Dt-1;
		} else {
			Dmin = Dt;
		}
	}
	test(Dmin);
	ll M = dlog.size();
	for (ll i=0;i<(K-M);i++) {
		dlog.push_back(Dmin+1);
	}
	sort(dlog.begin(),dlog.end());
	for (ll x: dlog) {
		cout << x << "\n";
	}
}

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