#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 {
struct Node {
Node *l, *r, *p;
int cnt;
int x;
static Node *nw() {
static Node pool[(1<<30)/sizeof(Node)];
static int p = 0;
return pool + p++;
}
};
vector<Node *> nodes;
static ll constexpr inf = 1e10;
Node *add(Node *t, ll p, int x, ll b, ll e) {
Node *ans = Node::nw();
ans->p = t;
ans->cnt = (t? t->cnt: 0) + 1;
ans->x = x;
if (e - b == 1)
return ans;
if (p < (b + e)/2) {
ans->l = add(t? t->l: 0, p, x, b, (b+e)/2);
ans->r = t? t->r: 0;
} else {
ans->l = t? t->l: 0;
ans->r = add(t? t->r: 0, p, x, (b+e)/2, e);
}
return ans;
}
void init(int n, vector<pll> vals) {
sort(vals.begin(), vals.end());
nodes = {nullptr};
auto it = vals.begin();
Loop (i,0,n) {
auto t = nodes.back();
while (it != vals.end() && it->first == i) {
t = add(t, it->second, i, -inf, inf);
it++;
}
nodes.push_back(t);
}
}
ll count(Node *t, ll l, ll r, ll b, ll e) {
if (r <= b || e <= l || !t)
return 0;
if (l <= b && e <= r)
return t->cnt;
return count(t->l, l, r, b, (b+e)/2) + count(t->r, l, r, (b+e)/2, e);
}
ll count(int l, int r, ll l2, ll r2) {
return count(nodes[r], l2, r2, -inf, inf) - count(nodes[l], l2, r2, -inf, inf);
}
static constexpr int val(const Node *t1, const Node *t2) { return (t2? t2->cnt: 0) - (t1? t1->cnt: 0); }
void list(Node *t1, Node *t2, vector<pll> &vec, ll l, ll r, ll b, ll e) {
if (r <= b || e <= l || val(t1, t2) == 0)
return;
if (e - b == 1) {
for (auto t = t2; t != t1; t = t->p)
vec.push_back({t->x, b});
return;
}
list(t1? t1->l: 0, t2? t2->l: 0, vec, l, r, b, (b+e)/2);
list(t1? t1->r: 0, t2? t2->r: 0, vec, l, r, (b+e)/2, e);
}
vector<pll> list(int l, int r, ll l2, ll r2) {
vector<pll> ans;
list(nodes[l], nodes[r], ans, l2, r2, -inf, inf);
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(1e9))
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 |
| 1 |
Incorrect |
94 ms |
14520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10077 ms |
303944 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10077 ms |
302152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10077 ms |
302152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
14520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
14520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
