Submission #1243799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243799		Matthewwww	Road Construction (JOI21_road_construction)	C++17	100 / 100	2067 ms	8324 KiB

road_construction

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif

int dist (pair<int, int> a, pair<int, int> b) {
	return max(abs(a.f-b.f), abs(a.s-b.s));
}

signed main (signed argc, char **argv) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> vt(n);
	for (auto &i: vt) cin >> i.f >> i.s;
	for (auto &i: vt) i = {i.f-i.s, i.f+i.s};
	sort(vt.begin(), vt.end());
	int len = 0;
	for (int bt = 40; bt--;) {
		int m = len+(1ll<<bt);
		int cnt = 0;
		set<pair<int, int>> st;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		int upto = 0;
		for (auto i: vt) {
			while (pq.size() && pq.top().f < i.f-m) {
				st.erase({vt[pq.top().s].s, pq.top().s});
				pq.pop();
			}
			cnt += distance(st.lower_bound({i.s-m, 0}), st.upper_bound({i.s+m, n}));
			if (cnt >= k) break;
			st.insert({i.s, upto});
			pq.push({i.f, upto++});
		}
		if (cnt < k) len = m;
	}
	vector<int> ans;
	set<pair<int, int>> st;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int upto = 0;
	for (auto i: vt) {
		while (pq.size() && pq.top().f < i.f-len) {
			st.erase({vt[pq.top().s].s, pq.top().s});
			pq.pop();
		}
		for (auto j = st.lower_bound({i.s-len, 0}); j != st.upper_bound({i.s+len, n}); ++j) 
			ans.push_back(dist(i, vt[(*j).s]));
		st.insert({i.s, upto});
		pq.push({i.f, upto++});
	}
	int left = k-(int)ans.size();
	sort(ans.begin(), ans.end());
	for (int i: ans) cout << i << "\n";
	while (left--) cout << len+1 << "\n";
}

/*
 *
 *  ┏┓   ┏┓+ +
 * ┏┛┻━━━┛┻┓ + +
 * ┃   ━   ┃ ++ + + +
 * ████━████+
 * ◥██◤ ◥██◤ +
 * ┃   ┻   ┃ 
 * ┗━┓   ┏━┛  + + 
 *   ┃   ┃ + + + +Code is far away from  
 *   ┃   ┃ + bug with the llama protecting
 *   ┃    ┗━━━┓ 神兽保佑,代码无bug 
 *   ┃        ┣┓
 *   ┃        ┏┛
 *   ┗┓┓┏━┳┓┏┛ + + + +
 *    ┃┫┫ ┃┫┫
 *    ┗┻┛ ┗┻┛+ + + +
 */

//thanks cindy

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