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>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
struct Seg {
vector<vector<pll>> ys;
int n;
static bool cmp(const pll &a, const pll &b) {
return a.second < b.second;
}
void init(const pll *&ptr, const pll *end, int i, int b, int e)
{
if (e - b == 1) {
ys[i].clear();
while (ptr != end && ptr->first == b)
ys[i].push_back(*ptr++);
return;
}
init(ptr, end, 2*i+1, b, (b+e)/2);
init(ptr, end, 2*i+2, (b+e)/2, e);
ys[i].resize(ys[2*i+1].size() + ys[2*i+2].size());
merge(ys[2*i+1].begin(), ys[2*i+1].end(),
ys[2*i+2].begin(), ys[2*i+2].end(),
ys[i].begin(), cmp);
}
void init(int n, vector<pll> vals) {
this->n = n;
ys.resize(n*4);
sort(vals.begin(), vals.end());
const pll *ptr = vals.data();
init(ptr, ptr + vals.size(), 0, 0, n);
}
typedef decltype(ys[0].begin()) iter;
template<class Fn>
void range_query(Fn fn, int l, int r, ll l2, ll r2, int i, int b, int e) {
if (l <= b && e <= r) {
iter it1 = lower_bound(ys[i].begin(), ys[i].end(), pll{INT_MIN, l2}, cmp);
iter it2 = lower_bound(ys[i].begin(), ys[i].end(), pll{INT_MIN, r2}, cmp);
return fn(it1, it2);
}
if (r <= b || e <= l)
return;
range_query(fn, l, r, l2, r2, 2*i+1, b, (b+e)/2);
range_query(fn, l, r, l2, r2, 2*i+2, (b+e)/2, e);
}
ll count(int l, int r, ll l2, ll r2) {
ll ans = 0;
range_query([&](iter it1, iter it2) { ans += it2 - it1; }, l, r, l2, r2, 0, 0, n);
return ans;
}
vector<pll> list(int l, int r, ll l2, ll r2) {
vector<pll> ans;
range_query([&](iter it1, iter it2) { ans.insert(ans.end(), it1, it2); }, l, r, l2, r2, 0, 0, n);
return ans;
}
};
struct CompSeg {
Seg seg;
vector<ll> xs;
int comp(ll x) { return lower_bound(xs.begin(), xs.end(), x) - xs.begin(); }
void init(vector<pll> vals) {
for (auto [x, _] : vals)
xs.push_back(x);
sort(xs.begin(), xs.end());
xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
vector<pll> cmped;
for (auto [x, y] : vals)
cmped.emplace_back(comp(x), y);
seg.init(xs.size(), cmped);
}
ll count(ll l, ll r, ll l2, ll r2) {
return seg.count(comp(l), comp(r), l2, r2);
}
vector<pll> list(ll l, ll r, ll l2, ll r2) {
auto vec = seg.list(comp(l), comp(r), l2, r2);
for (auto &[x, y] : vec)
x = xs[x];
return vec;
}
};
struct SquareSeg {
CompSeg seg;
vector<pll> vals;
static pll rot(const pll &p) {
return { p.first - p.second, p.first + p.second };
}
static pll unrot(const pll &p) {
assert((p.first + p.second) % 2 == 0);
return { (p.first + p.second)/2, (p.first - p.second)/2 };
}
void init(const vector<pll> &vals_) {
vals = vals_;
for (auto &p : vals)
p = rot(p);
seg.init(vals);
}
ll count(ll l) {
ll sum = 0;
for (auto [x, y] : vals)
sum += seg.count(x - l, x + l + 1, y - l, y + l + 1);
sum -= vals.size();
sum /= 2;
return sum;
}
auto list(ll l) {
vector<pair<pll,pll>> vec;
for (auto p1 : vals) {
auto &[x, y] = p1;
auto vec2 = seg.list(x - l, x + l + 1, y - l, y + l + 1);
for (auto p2 : vec2) {
if (p1 < p2)
vec.emplace_back(unrot(p1), unrot(p2));
}
}
return vec;
}
};
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int n, k;
cin >> n >> k;
vector<ll> ans(k);
vector<pll> vals(n);
for (auto &[x, y] : vals)
cin >> x >> y;
SquareSeg seg;
seg.init(vals);
ll l = 0, r = 4.2e9;
while (l < r) {
ll m = (l + r + 1)/2;
if (seg.count(m) < k)
l = m;
else
r = m-1;
}
vector<ll> vec;
for (auto [p1, p2] : seg.list(l))
vec.push_back(abs(p1.first - p2.first) + abs(p1.second - p2.second));
sort(vec.begin(), vec.end());
vec.resize(k, l + 1);
for (ll x : vec)
cout << x << '\n';
}
# | 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... |