#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<ll, 3>
const int inf = 1e9;
const int nn = 5e5 + 5;
struct FT{
vector<int> bit, ch;
int n;
void init(int ns){
n = ns;
bit.resize(n + 1);
}
void upd(int p, int k){
while (p <= n){
bit[p] += k;
ch.pb(p);
p |= (p + 1);
}
}
int get(int v){
v--;
int out = 0;
while (v > 0){
out += bit[v];
v = (v & (v + 1)) - 1;
}
return out;
}
void clear(){
for (int i: ch) bit[i] = 0;
ch.clear();
}
};
struct TDC{
struct data{
int t, x, y, k;
};
vector<data> qs;
FT T;
TDC(int nn){
T.init(nn);
}
void add_p(int x, int y){
qs.pb({1, x, y});
}
void add_q(int x1, int x2, int y1, int y2){ // x є [x1, x2], y є [y1, y2]
if (x1 > x2 || y1 > y2) return;
qs.pb({0, x2 + 1, y2 + 1, 1});
qs.pb({0, x1, y1, 1});
qs.pb({0, x1, y2 + 1, -1});
qs.pb({0, x2 + 1, y1, -1});
}
ll solve(int l, int r){
if (l == r) return 0;
int m = (l + r) / 2;
ll sum = 0;
vector<data> lf, rt;
for (int i = l; i <= m; i++){
if (qs[i].t != 0){
lf.pb(qs[i]);
}
}
for (int i = m + 1; i <= r; i++){
if (!qs[i].t){
rt.pb(qs[i]);
}
}
auto cmp = [&](data& a, data& b){
return a.x < b.x;
};
sort(lf.begin(), lf.end(), cmp);
sort(rt.begin(), rt.end(), cmp);
int i = 0, j = 0;
while (j < rt.size()){
while (i < lf.size() && lf[i].x < rt[j].x){
T.upd(lf[i].y, lf[i].t);
i++;
}
sum += rt[j].k * T.get(rt[j].y);
j++;
}
T.clear();
return sum + solve(l, m) + solve(m + 1, r);
}
ll solve(){
ll out = solve(0, (int) qs.size() - 1);
qs.clear();
return out;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k; cin>>n>>k;
vector<int> x(n + 1), y(n + 1), all;
for (int i = 1; i <= n; i++){
cin>>x[i]>>y[i];
all.pb(x[i]);
all.pb(y[i]);
}
sort(all.begin(), all.end());
int i = 0, cnt = 0;
map<int, int> mp;
while (i < all.size()){
int j = i;
while (j < all.size() && all[i] == all[j]) j++;
mp[all[i]] = ++cnt;
i = j;
}
vector<int> xp(n + 1), yp(n + 1);
for (int i = 1; i <= n; i++){
xp[i] = mp[x[i]];
yp[i] = mp[y[i]];
}
TDC T(cnt);
auto count = [&](ll d){ // #(1 <= i < j <= n) : abs(xi - xj) + abs(yi - yj) <= d
ll out = -n;
auto cmp = [&](arr3& a, arr3& b){
if (a[0] == b[0]){
return a[2] < b[2];
}
return a[0] > b[0];
};
// xi >= xj, yi >= yj: xi - xj + yi - yj <= d <-> xi + yi - d <= xj + yj
vector<arr3> st;
for (int i = 1; i <= n; i++){
st.pb({x[i] + y[i], i, 0});
st.pb({x[i] + y[i] - d, i, 1});
}
sort(st.begin(), st.end(), cmp);
for (auto p: st){
if (!p[2]){
T.add_p(xp[p[1]], yp[p[1]]);
continue;
}
T.add_q(1, xp[p[1]], 1, yp[p[1]]);
}
out += T.solve();
// xi >= xj, yi < yj: xi - xj + yj - yi <= d <-> xi - yi - d <= xj - yj
st.clear();
for (int i = 1; i <= n; i++){
st.pb({x[i] - y[i], i, 0});
st.pb({x[i] - y[i] - d, i, 1});
}
sort(st.begin(), st.end(), cmp);
for (auto p: st){
if (!p[2]){
T.add_p(xp[p[1]], yp[p[1]]);
continue;
}
T.add_q(1, xp[p[1]], yp[p[1]] + 1, cnt);
}
out += T.solve();
// xi < xj, yi >= yj: xj - xi + yi - yj <= d <-> yi - xi - d <= yj - xj
st.clear();
for (int i = 1; i <= n; i++){
st.pb({y[i] - x[i], i, 0});
st.pb({y[i] - x[i] - d, i, 1});
}
sort(st.begin(), st.end(), cmp);
for (auto p: st){
if (!p[2]){
T.add_p(xp[p[1]], yp[p[1]]);
continue;
}
T.add_q(xp[p[1]] + 1, cnt, 1, yp[p[1]]);
}
out += T.solve();
// xi < xj, yi < yj: xj - xi + yj - yi <= d <-> -(xi + yi + d) <= -(xj + yj)
st.clear();
for (int i = 1; i <= n; i++){
st.pb({-(x[i] + y[i]), i, 0});
st.pb({-(x[i] + y[i] + d), i, 1});
}
sort(st.begin(), st.end(), cmp);
for (auto p: st){
if (!p[2]){
T.add_p(xp[p[1]], yp[p[1]]);
continue;
}
T.add_q(xp[p[1]] + 1, cnt, yp[p[1]] + 1, cnt);
}
out += T.solve();
return out / 2;
};
ll l = 0, r = 4LL * inf;
while (l + 1 < r){
ll m = (l + r) / 2;
if (count(m) < k){
l = m + 1;
}
else {
r = m;
}
}
// find all pairs with MHD <= r
vector<pii> p(n + 1);
for (int i = 1; i <= n; i++){
p[i] = {x[i], y[i]};
}
sort(p.begin() + 1, p.end());
multiset<pii> st;
vector<ll> dist;
int j = 1;
for (int i = 1; i <= n; i++){
while (j < i && (p[i].ff - p[j].ff) > r){
st.erase(st.find(p[j]));
j++;
}
auto it = st.lower_bound({-inf, p[i].ss - r});
ll R = p[i].ss + r;
while (it != st.end() && (*it).ss <= R){
ll d = abs(p[i].ff - (*it).ff) + abs(p[i].ss - (*it).ss);
if (d <= r){
dist.pb(d);
}
it++;
}
st.insert(p[i]);
}
sort(dist.begin(), dist.end());
for (int i = 0; i < k; i++){
cout<<dist[i]<<"\n";
}
}
// Looks like O(n * log^3(n) + ?) is very fast!
Compilation message
road_construction.cpp: In member function 'll TDC::solve(int, int)':
road_construction.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TDC::data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (j < rt.size()){
| ~~^~~~~~~~~~~
road_construction.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TDC::data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | while (i < lf.size() && lf[i].x < rt[j].x){
| ~~^~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | while (i < all.size()){
| ~~^~~~~~~~~~~~
road_construction.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | while (j < all.size() && all[i] == all[j]) j++;
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
210 ms |
4288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
10069 ms |
114284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
10056 ms |
125788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
10056 ms |
125788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
210 ms |
4288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
210 ms |
4288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
