This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 250000;
vector<long long> tbc;
void compress() {sort(tbc.begin(), tbc.end()); tbc.resize(unique(tbc.begin(), tbc.end()) - tbc.begin());}
int order(long long key) {return lower_bound(tbc.begin(), tbc.end(), key) - tbc.begin() + 1;}
struct Binary_Indexed_Tree {
int bit[N * 3 + 8];
Binary_Indexed_Tree() {memset(bit, 0, sizeof bit);}
void reset() {memset(bit, 0, sizeof bit);}
int pt;
void update(int u) {
pt = u;
while (pt <= N * 3) {
++bit[pt];
pt += (pt & -pt);
}
}
int res;
int pf(int u) {
if (u <= 0) return 0;
pt = u; res = 0;
while (pt) {
res += bit[pt];
pt -= (pt & -pt);
}
return res;
}
int range(int l, int r) {return pf(r) - pf(l - 1);}
} tree;
void rotate_45(pair<long long, long long>& pt) {pt.fi -= pt.se; pt.se += pt.fi + pt.se;}
void rotate_45(pair<int, int>& pt) {pt.fi -= pt.se; pt.se += pt.fi + pt.se;}
pair<long long, long long> raw[N + 8];
pair<int, int> A[N + 8];
pair<int, int> range_x[N + 8], range_y[N + 8];
vector<tuple<int, int, int>> Oy_Q[N * 3 + 8];
vector<int> Oy_U[N * 3 + 8];
int n;
void compress_all(long long radius) {
tbc.clear();
for (int i = 1; i <= n; ++i) tbc.push_back(raw[i].fi);
for (int i = 1; i <= n; ++i) {
tbc.push_back(raw[i].fi - radius - 1);
tbc.push_back(raw[i].fi + radius);
}
compress();
for (int i = 1; i <= n; ++i) A[i].fi = order(raw[i].fi);
for (int i = 1; i <= n; ++i) range_x[i] = make_pair(order(raw[i].fi - radius - 1), order(raw[i].fi + radius));
tbc.clear();
for (int i = 1; i <= n; ++i) tbc.push_back(raw[i].se);
for (int i = 1; i <= n; ++i) {
tbc.push_back(raw[i].se - radius);
tbc.push_back(raw[i].se + radius);
}
compress();
for (int i = 1; i <= n; ++i) A[i].se = order(raw[i].se);
for (int i = 1; i <= n; ++i) range_y[i] = make_pair(order(raw[i].se - radius - 1), order(raw[i].se + radius));
for (int i = 1; i <= n; ++i) {
Oy_U[A[i].fi].push_back(A[i].se);
Oy_Q[range_x[i].fi].push_back({range_y[i].fi, range_y[i].se, -1});
Oy_Q[range_x[i].se].push_back({range_y[i].fi, range_y[i].se, +1});
}
}
int ly, ry, coef; long long res;
long long C(long long radius) {
res = -n; compress_all(radius);
for (int x = 1; x <= N * 3; ++x) {
for (int y : Oy_U[x]) tree.update(y);
for (auto item : Oy_Q[x]) {
tie(ly, ry, coef) = item;
res += tree.range(ly, ry) * coef;
}
}
for (int i = 1; i <= N * 3; ++i) Oy_Q[i].clear(), Oy_U[i].clear();
tree.reset();
return res / 2;
}
map<long long, int> f;
vector<int> Oy[N * 3 + 8];
long long dist(pair<long long, long long>& A1, pair<long long, long long>& A2) {return max(abs(A1.fi - A2.fi), abs(A1.se - A2.se));}
long long dist(int i, int j) {return dist(raw[i], raw[j]);}
multiset<pair<int, int>> active; int lx, rx; multiset<pair<int, int>>::iterator it;
void find_all_connections(long long radius) {
compress_all(radius); lx = 0; rx = 0;
for (int i = 1; i <= n; ++i) Oy[A[i].fi].push_back(i);
for (int i = 1; i <= n; ++i) {
while (rx < range_x[i].second) {
++rx;
for (int id : Oy[rx]) active.insert({A[id].se, id});
}
while (lx < range_x[i].fi) {
for (int id : Oy[lx]) active.erase(active.find({A[id].se, id}));
++lx;
}
it = active.lower_bound({range_y[i].first, 0});
for (; it != active.end() && it->fi <= range_y[i].second; ++it)
++f[dist(i, it->second)];
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int k; cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> raw[i].fi >> raw[i].se, rotate_45(raw[i]);
sort(raw + 1, raw + n + 1);
long long l = 1, r = 1e10, mid;
while (l <= r) {
mid = (l + r) / 2;
if (C(mid) < k) l = mid + 1;
else r = mid - 1;
}
// cout << l << '\n';
find_all_connections(l - 1); int cnt = 0; f.erase(0);
for (auto item : f) {
cnt += (item.second) / 2;
for (int i = 0; i < item.second / 2; ++i) cout << item.first << '\n';
}
while (cnt < k) cout << l << '\n', ++cnt;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |