#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint inf = 1e18;
namespace Persistent {
struct Node {
int sum = 0;
int lc = 0;
int rc = 0;
};
const int MAX_SIZE = 1e7;
int node_cnt = 1;
Node node[MAX_SIZE];
int NewNode() {
return node_cnt++;
}
int CopyNode(int n) {
node[node_cnt] = node[n];
return node_cnt++;
}
int Build(int tl, int tr) {
int n = NewNode();
if (tl == tr) return n;
int md = (tl + tr) / 2;
node[n].lc = Build(tl, md);
node[n].rc = Build(md + 1, tr);
return n;
}
int Update(int n, int tl, int tr, int p, int x) {
n = CopyNode(n);
if (tl == tr) {
node[n].sum += x;
return n;
}
int md = (tl + tr) / 2;
node[n].sum += x;
if (p <= md) {
node[n].lc = Update(node[n].lc, tl, md, p, x);
} else {
node[n].rc = Update(node[n].rc, md + 1, tr, p, x);
}
return n;
}
int Query(int n, int tl, int tr, int l, int r) {
if (tl > r || l > tr || tl > tr || l > r) return 0;
if (l <= tl && tr <= r) return node[n].sum;
int md = (tl + tr) / 2;
return Query(node[n].lc, tl, md, l, r) + Query(node[n].rc, md + 1, tr, l, r);
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<lint> X(N), Y(N);
vector<lint> coordX = {-inf, inf}, coordY = {-inf, inf};
for (int i = 0; i < N; i++) {
cin >> X[i] >> Y[i];
tie(X[i], Y[i]) = pair(X[i] + Y[i], X[i] - Y[i]);
coordX.emplace_back(X[i]);
coordY.emplace_back(Y[i]);
}
sort(begin(coordX), end(coordX));
sort(begin(coordY), end(coordY));
coordX.resize(unique(begin(coordX), end(coordX)) - begin(coordX));
coordY.resize(unique(begin(coordY), end(coordY)) - begin(coordY));
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), [&](int i, int j) { return X[i] < X[j]; });
vector<int> tree(coordX.size());
int prv = tree[0] = Persistent::Build(0, int(coordY.size()) - 1);
for (auto i : ord) {
int xid = lower_bound(begin(coordX), end(coordX), X[i]) - begin(coordX);
int yid = lower_bound(begin(coordY), end(coordY), Y[i]) - begin(coordY);
tree[xid] = Persistent::Update(prv, 0, int(coordY.size()) - 1, yid, 1);
prv = tree[xid];
}
const auto Count = [&](int i, lint dist) {
int xlo = lower_bound(begin(coordX), end(coordX), X[i] - dist) - begin(coordX);
int xhi = upper_bound(begin(coordX), end(coordX), X[i] + dist) - begin(coordX) - 1;
int ylo = lower_bound(begin(coordY), end(coordY), Y[i] - dist) - begin(coordY);
int yhi = upper_bound(begin(coordY), end(coordY), Y[i] + dist) - begin(coordY) - 1;
return Persistent::Query(tree[xhi], 0, int(coordY.size()) - 1, ylo, yhi) -
Persistent::Query(tree[xlo - 1], 0, int(coordY.size()) - 1, ylo, yhi);
};
vector<lint> ans;
priority_queue<array<lint, 3>, vector<array<lint, 3>>, greater<array<lint, 3>>> pq; // (dist, #copy, source)
vector<lint> dist(N);
const auto Relax = [&](int i) {
lint count_old = Count(i, dist[i]);
lint lo = dist[i] + 1, hi = 1e10;
while (lo < hi) {
lint md = (lo + hi) / 2;
if (Count(i, md) - count_old > 0) {
hi = md;
} else {
lo = md + 1;
}
}
dist[i] = lo;
pq.push({lo, Count(i, lo) - count_old, i});
};
for (int i = 0; i < N; i++) {
Relax(i);
}
while (ans.size() < 2 * K) {
auto top = pq.top(); pq.pop();
ans.emplace_back(top[0]); top[1]--;
if (top[1] > 0) {
pq.emplace(top);
} else {
Relax(top[2]);
}
}
assert(ans.size() == 2 * K);
for (int i = 0; i < K; i++) {
assert(ans[i * 2] == ans[i * 2 + 1]);
cout << ans[i * 2] << '\n';
}
return 0;
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:71:27: error: missing template arguments before '(' token
71 | tie(X[i], Y[i]) = pair(X[i] + Y[i], X[i] - Y[i]);
| ^
road_construction.cpp:128:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
128 | while (ans.size() < 2 * K) {
| ~~~~~~~~~~~^~~~~~~
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from road_construction.cpp:1:
road_construction.cpp:138:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
138 | assert(ans.size() == 2 * K);
| ~~~~~~~~~~~^~~~~~~~
