#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 PersSeg {
struct Node {
Node *l, *r;
int cnt;
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, ll b, ll e) {
Node *ans = Node::nw();
ans->cnt = (t? t->cnt: 0) + 1;
if (e - b == 1)
return ans;
if (p < (b + e)/2) {
ans->l = add(t? t->l: 0, p, 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, (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, -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); }
};
struct VecSeg {
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);
}
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 Seg {
PersSeg pseg;
VecSeg vseg;
void init(int n, const vector<pll> &vals) {
pseg.init(n, vals);
vseg.init(n, vals);
}
ll count(int l, int r, ll l2, ll r2) {
return pseg.count(l, r, l2, r2);
}
vector<pll> list(int l, int r, ll l2, ll r2) {
return vseg.list(l, r, l2, r2);
}
};
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 |
35 ms |
15572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10111 ms |
1432796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10041 ms |
336376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10041 ms |
336376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
15572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
15572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
