#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;
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 q = ids[node].size() - 1; q >= 0; q--) {
int id = ids[node][q];
if (dx[id] <= dx[i] - high) {
break;
}
ans.push_back(abs(x[i] - x[id]) + abs(y[i] - y[id]));
// cout << i + 1 << " " << id + 1 << " " << ans.back() << endl;
}
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;
};
assert(false);
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:113:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
113 | int mid = l + r >> 1;
| ~~^~~
road_construction.cpp: In lambda function:
road_construction.cpp:147:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:158:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
158 | while (ans.size() < k) {
| ~~~~~~~~~~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
28 ms |
1380 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
8026 ms |
155236 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
10046 ms |
58652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
10046 ms |
58652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
28 ms |
1380 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
28 ms |
1380 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
