#include <bits/stdc++.h>
using namespace std;
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> x(n);
vector<int> y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
auto Count = [&](long long d) {
vector<tuple<long long, int, long long, long long>> ev;
vector<long long> xs;
for (int i = 0; i < n; i++) {
long long dx = x[i] + y[i];
long long dy = x[i] - y[i];
ev.emplace_back(dx - d, 0, dy - d - 1, dy + d);
ev.emplace_back(dx + d + 1, 1, dy - d - 1, dy + d);
ev.emplace_back(dx, 2, dy, dy);
xs.push_back(dy - d - 1);
xs.push_back(dy + d);
xs.push_back(dy);
}
sort(ev.begin(), ev.end());
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
int sz = xs.size();
fenwick<int> fenw(sz);
long long cnt = 0;
for (auto& e : ev) {
int t = get<1>(e);
if (t == 0) {
int L = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
int R = lower_bound(xs.begin(), xs.end(), get<3>(e)) - xs.begin();
cnt -= fenw.get(R) - fenw.get(L);
} else if (t == 1) {
int L = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
int R = lower_bound(xs.begin(), xs.end(), get<3>(e)) - xs.begin();
cnt += fenw.get(R) - fenw.get(L);
} else {
int aa = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
fenw.modify(aa, +1);
}
}
return (cnt - n) / 2;
};
long long low = 0, high = 4.1e9;
while (low + 1 < high) {
long long mid = (low + high + 1) >> 1;
if (Count(mid) >= k) {
high = mid;
} else {
low = mid;
}
}
vector<long long> ans;
vector<vector<int>> ids(12 * n);
function<void(int, int, int, int, int)> add = [&](int node, int l, int r, int i, int id) {
ids[node].push_back(id);
if (l == r) {
return;
}
int mid = l + r >> 1;
if (i <= mid) {
add(node + node, l, mid, i, id);
} else {
add(node + node + 1, mid + 1, r, i, id);
}
};
vector<long long> dx(n);
vector<long long> dy(n);
function<void(int, int, int, int, int, int)> solve = [&](int node, int l, int r, int ll, int rr, int i) {
if (l > r || l > rr || r < ll) return;
if (ll <= l && r <= rr) {
for (int id : ids[node]) {
if (dx[id] <= dx[i] - high) {
break;
}
ans.push_back(abs(x[i] - x[id]) + abs(y[i] - y[id]));
}
return;
}
int mid = l + r >> 1;
solve(node + node, l, mid, ll, rr, i);
solve(node + node + 1, mid + 1, r, ll, rr, i);
};
function<void(long long)> Construct = [&](long long d) {
vector<tuple<long long, int, long long>> ev;
vector<long long> xs;
for (int i = 0; i < n; i++) {
dx[i] = x[i] + y[i];
dy[i] = x[i] - y[i];
ev.emplace_back(dx[i], 0, i);
ev.emplace_back(dx[i] + d, 1, i);
xs.push_back(dy[i] - d);
xs.push_back(dy[i] + d);
xs.push_back(dy[i]);
}
sort(ev.begin(), ev.end());
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
int sz = xs.size();
for (auto& e : ev) {
int t = get<1>(e);
int idx = get<2>(e);
if (t == 0) {
int aa = lower_bound(xs.begin(), xs.end(), dy[idx]) - xs.begin();
add(1, 0, sz - 1, aa, idx);
} else {
int L = lower_bound(xs.begin(), xs.end(), dy[idx] - d) - xs.begin();
int R = lower_bound(xs.begin(), xs.end(), dy[idx] + d) - xs.begin();
solve(1, 0, sz - 1, L, R, idx);
}
}
sort(ans.begin(), ans.end());
vector<long long> tmp;
for (int i = 0; i < ans.size(); i++) {
if (ans[i] == 0) {
continue;
}
tmp.push_back(ans[i]);
i += 1;
}
ans = tmp;
};
Construct(high - 1);
while (ans.size() < k) {
ans.push_back(high);
}
for (int i = 0; i < k; i++) {
if (i > 0) {
cout << '\n';
}
cout << ans[i];
}
cout << '\n';
return 0;
}
Compilation message
road_construction.cpp: In lambda function:
road_construction.cpp:91:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | int mid = l + r >> 1;
| ~~^~~
road_construction.cpp: In lambda function:
road_construction.cpp:111:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | int mid = l + r >> 1;
| ~~^~~
road_construction.cpp: In lambda function:
road_construction.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:155:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
155 | while (ans.size() < k) {
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7952 ms |
146888 KB |
Output is correct |
| 2 |
Correct |
8186 ms |
146668 KB |
Output is correct |
| 3 |
Correct |
73 ms |
8588 KB |
Output is correct |
| 4 |
Correct |
7917 ms |
148972 KB |
Output is correct |
| 5 |
Correct |
7860 ms |
149344 KB |
Output is correct |
| 6 |
Correct |
7896 ms |
149400 KB |
Output is correct |
| 7 |
Correct |
7948 ms |
143752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10008 ms |
58900 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10008 ms |
58900 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
