제출 #1297867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297867		kian2009	Road Construction (JOI21_road_construction)	C++20	100 / 100	1429 ms	8328 KiB

road_construction

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

ll n, k;
pll p[MAXN];
vector<ll> res;
set<pll> s;

void input() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		ll x, y;
		cin >> x >> y;
		p[i].f = x + y;
		p[i].s = x - y;
	}
	sort(p, p + n);
}

ll dist(int i, int j) {
	return max(abs(p[i].f - p[j].f), abs(p[i].s - p[j].s));	
}

bool check(ll x) {
	res.clear();
	s.clear();
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		while (cnt < i && p[i].f - p[cnt].f > x) {
			s.erase({p[cnt].s, cnt});
			cnt++;	
		}
		if (!s.empty()) {
			auto h = s.lower_bound({p[i].s - x, -1});
			for (; h != s.end(); h++) {
				if (p[(*h).s].s > p[i].s + x)
					break;
				res.push_back(dist((*h).s, i));
				if (res.size() >= k)
					return true;
			}
		}
		s.insert({p[i].s, i});
	}
	return false;
}

void findAns() {
	ll l = 0, r = 4e9;
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}
	check(l);
	sort(res.begin(), res.end());
	for (auto x : res)
		cout << x << '\n';
	for (int i = 0; i < k - (int)res.size(); i++)
		cout << r << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	findAns();
	return 0;
}

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