#include "bits/stdc++.h"
using namespace std;
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type,
less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ar array
#define int long long
const int N = 75e4 + 5;
struct BIT{
int tree[N];
void add(int i, int v){ i++;
for(;i<N;i+=(i&-i)) tree[i] += v;
}
int get(int i){ i++;
int r = 0;
for(;i>0;i-=(i&-i)) r += tree[i];
return r;
}
int get(int l, int r) { return get(r) - get(l - 1); }
}bit;
vector<int> rr;
int a[N][2];
int Dis(int i, int j){
return abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]);
}
struct ST{
set<int> tree[1 << 21];
void add(int l, int r, int i, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){ tree[x].insert(i); return; }
int m = (lx + rx) >> 1;
add(l, r, i, lx, m, x<<1);
add(l, r, i, m+1, rx, x<<1|1);
}
void del(int l, int r, int i, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r) { tree[x].erase(i); return; }
int m = (lx + rx) >> 1;
del(l, r, i, lx, m, x<<1);
del(l, r, i, m+1, rx, x<<1|1);
}
void get(int I, int i, int lx = 0, int rx = N, int x = 1){
for(auto j : tree[x]){
if(i < j) rr.push_back(Dis(i, j));
}
if(lx == rx) return;
int m = (lx + rx) >> 1;
if(I <= m) get(I, i, lx, m, x<<1);
else get(I, i, m+1, rx, x<<1|1);
}
}T;
int n, k, p[N][2];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1];
vector<int> q(n), ip(n), op(n);
for(int i=0;i<n;i++){
p[i][0] = a[i][0] + a[i][1];
p[i][1] = a[i][0] - a[i][1];
q[i] = ip[i] = op[i] = i;
}
int d = -1;
{
auto check = [&](int d){
memset(bit.tree, 0, sizeof bit.tree);
vector<ar<int, 2>> x, y;
vector<ar<int, 3>> in, out;
for(int i=0;i<n;i++){
in.push_back({p[i][0] - d, p[i][1] - d, p[i][1] + d});
out.push_back({p[i][0] + d, p[i][1] - d, p[i][1] + d});
//~ x.push_back({p[i][0], i << 2});
//~ x.push_back({p[i][0] - d, i << 2 | 1});
//~ x.push_back({p[i][0] + d, i << 2 | 2});
//~ y.push_back({p[i][1], i << 2});
//~ y.push_back({p[i][1] - d, i << 2 | 1});
//~ y.push_back({p[i][1] + d, i << 2 | 2});
}
//~ sort(x.begin(), x.end());
//~ sort(y.begin(), y.end());
//~ for(int i=0, last=0;i<(int)x.size();){
//~ int j = i;
//~ while(j < (int)x.size() && x[j][0] == x[i][0]){
//~ if((x[j][1]&3) == 0){
//~ p[x[j][1] >> 2][0] = last;
//~ } if((x[j][1]&3) == 1){
//~ in[x[j][1] >> 2][0] = last;
//~ } if((x[j][1]&3) == 2){
//~ out[x[j][1] >> 2][0] = last;
//~ } j++;
//~ } i = j; last++;
//~ }
//~ for(int i=0, last=0;i<(int)y.size();){
//~ int j = i;
//~ while(j < (int)y.size() && y[j][0] == y[i][0]){
//~ if((y[j][1]&3) == 0){
//~ p[y[j][1] >> 2][1] = last;
//~ } if((y[j][1]&3) == 1){
//~ in[y[j][1] >> 2][1] =
//~ out[y[j][1] >> 2][1] = last;
//~ } if((y[j][1]&3) == 2){
//~ in[y[j][1] >> 2][2] =
//~ out[y[j][1] >> 2][2] = last;
//~ } j++;
//~ } i = j, last++;
//~ }
int res = 0;
sort(in.begin(), in.end()),
sort(out.begin(), out.end());
sort(q.begin(), q.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
int j=0, k=0;
oset<int> bit;
for(auto i : q){
while(j < n && p[i][0] >= in[j][0]){
res -= (bit.order_of_key(in[j][2] + 1) - bit.order_of_key(in[j][1]));
j++;
} while(k < n && p[i][0] > out[k][0]){
res += (bit.order_of_key(out[k][2] + 1) - bit.order_of_key(out[k][1]));
//~ res += bit.get(out[k][1], out[k][2]);
k++;
} bit.insert(p[i][1]);
}
while(j < n) res -= (bit.order_of_key(in[j][2] + 1) - bit.order_of_key(in[j][1])), j++;
while(k < n) res += (bit.order_of_key(out[k][2] + 1) - bit.order_of_key(out[k][1])), k++;
res = (res - n) >> 1;
return (res >= ::k);
};
int l = 1, r = 4e9;
while(l < r){
int m = (l + r) >> 1;
if(check(m)) r = m;
else l = m + 1;
} d = l;
}
int D = d; d--;
vector<ar<int, 2>> p(n), x, y;
vector<ar<int, 3>> in, out;
for(int i=0;i<n;i++){
p[i][0] = a[i][0] + a[i][1];
p[i][1] = a[i][0] - a[i][1];
in.push_back({p[i][0] - d, p[i][1] - d, p[i][1] + d});
out.push_back({p[i][0] + d, p[i][1] - d, p[i][1] + d});
x.push_back({p[i][0], i << 2});
x.push_back({p[i][0] - d, i << 2 | 1});
x.push_back({p[i][0] + d, i << 2 | 2});
y.push_back({p[i][1], i << 2});
y.push_back({p[i][1] - d, i << 2 | 1});
y.push_back({p[i][1] + d, i << 2 | 2});
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
for(int i=0, last=0;i<(int)x.size();){
int j = i;
while(j < (int)x.size() && x[j][0] == x[i][0]){
if((x[j][1]&3) == 0){
p[x[j][1] >> 2][0] = last;
} if((x[j][1]&3) == 1){
in[x[j][1] >> 2][0] = last;
} if((x[j][1]&3) == 2){
out[x[j][1] >> 2][0] = last;
} j++;
} i = j; last++;
}
for(int i=0, last=0;i<(int)y.size();){
int j = i;
while(j < (int)y.size() && y[j][0] == y[i][0]){
if((y[j][1]&3) == 0){
p[y[j][1] >> 2][1] = last;
} else {
in[y[j][1] >> 2][y[j][1]&3] =
out[y[j][1] >> 2][y[j][1]&3] = last;
} j++;
} i = j, last++;
}
sort(ip.begin(), ip.end(), [&](int i, int j) { return (in[i][0] < in[j][0]); });
sort(op.begin(), op.end(), [&](int i, int j) { return (out[i][0] < out[j][0]); });
sort(q.begin(), q.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
int j=0, l=0;
for(auto i : q){
while(j<n && in[ip[j]][0] <= p[i][0]){
T.add(in[ip[j]][1], in[ip[j]][2], ip[j]);
j++;
} while(l<n && out[op[l]][0] < p[i][0]){
T.del(out[op[l]][1], out[op[l]][2], op[l]);
l++;
} T.get(p[i][1], i);
}
while((int)rr.size() < k) rr.push_back(D);
assert((int)rr.size() == k);
sort(rr.begin(), rr.end());
for(auto x : rr) cout<<x<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
109940 KB |
Output is correct |
| 2 |
Correct |
116 ms |
109924 KB |
Output is correct |
| 3 |
Correct |
108 ms |
110008 KB |
Output is correct |
| 4 |
Correct |
107 ms |
109948 KB |
Output is correct |
| 5 |
Correct |
113 ms |
108720 KB |
Output is correct |
| 6 |
Correct |
75 ms |
104996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10091 ms |
155512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10076 ms |
151112 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10076 ms |
151112 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
109940 KB |
Output is correct |
| 2 |
Correct |
116 ms |
109924 KB |
Output is correct |
| 3 |
Correct |
108 ms |
110008 KB |
Output is correct |
| 4 |
Correct |
107 ms |
109948 KB |
Output is correct |
| 5 |
Correct |
113 ms |
108720 KB |
Output is correct |
| 6 |
Correct |
75 ms |
104996 KB |
Output is correct |
| 7 |
Correct |
4705 ms |
140168 KB |
Output is correct |
| 8 |
Correct |
4789 ms |
139152 KB |
Output is correct |
| 9 |
Correct |
114 ms |
109964 KB |
Output is correct |
| 10 |
Correct |
4544 ms |
139208 KB |
Output is correct |
| 11 |
Correct |
4016 ms |
139356 KB |
Output is correct |
| 12 |
Correct |
3878 ms |
135056 KB |
Output is correct |
| 13 |
Correct |
3925 ms |
138708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
109940 KB |
Output is correct |
| 2 |
Correct |
116 ms |
109924 KB |
Output is correct |
| 3 |
Correct |
108 ms |
110008 KB |
Output is correct |
| 4 |
Correct |
107 ms |
109948 KB |
Output is correct |
| 5 |
Correct |
113 ms |
108720 KB |
Output is correct |
| 6 |
Correct |
75 ms |
104996 KB |
Output is correct |
| 7 |
Execution timed out |
10091 ms |
155512 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
