#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vei;
typedef vector<vei> vevei;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define con cout << "NO\n"
#define coe cout << "YES\n";
#define str string
#define pb push_back
#define ff first
#define sc second
#define ss second
#define pii pair<int, int>
#define mxe max_element
#define mne min_element
#define stf shrink_to_fit
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld
struct fenwick {
int n;
vector<int> t;
fenwick() = default;
fenwick(int n_) {
n = n_;
t.assign(n + 1, 0);
}
void clear() {
t.assign(n + 1, 0);
}
int sum(int x) {
int ans = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
ans += t[i];
}
return ans;
}
void upd(int pos, int delta) {
for (int i = pos; i < n; i = i | (i + 1)) {
t[i] += delta;
}
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k; cin >> n >> k;
vector<pair<ll, ll>> a(n);
for (int i = 0; i < n; i++) cin >> a[i].ff >> a[i].sc;
vector<pair<ll, ll>> b(n), xs(n), ys(n);
for (int i = 0; i < n; i++) {
b[i] = {a[i].ff - a[i].sc, a[i].ff + a[i].sc};
xs[i] = {b[i].ff, i};
ys[i] = {b[i].sc, i};
}
vector<int> posx(n), posy(n);
sort(all(xs));
sort(all(ys));
f (i, 0, n) {
posy[ys[i].sc] = i;
posx[xs[i].sc] = i;
}
ll L = -1, R = 4 * 1000ll * 1000ll * 1000ll;
vector<int> nextx(n), prevx(n), nexty(n), prevy(n);
vector<vector<int>> evs(n);
fenwick fw(n + 1);
while (R - L > 1) {
ll M = (L + R) / 2;
ll sm = 0;
int ind = 0;
f (i, 0, n) {
while (ind + 1 < n && xs[ind + 1].ff - xs[i].ff <= M) ind++;
nextx[i] = ind;
}
ind = n - 1;
for (int i = n - 1; i >= 0; i--) {
while (ind - 1 >= 0 && xs[i].ff - xs[ind - 1].ff <= M) ind--;
prevx[i] = ind;
}
ind = 0;
f(i, 0, n) {
while (ind + 1 < n && ys[ind + 1].ff - ys[i].ff <= M) ind++;
nexty[i] = ind;
}
ind = n - 1;
for (int i = n - 1; i >= 0; i--) {
while (ind - 1 >= 0 && ys[i].ff - ys[ind - 1].ff <= M) ind--;
prevy[i] = ind;
}
fw.clear();
for (int i = 0; i < n; i++) {
evs[prevx[posx[i]]].pb(i);
evs[nextx[posx[i]]].pb(i);
}
vector<int> ans(n);
f (i, 0, n) {
for (auto &u : evs[i]) {
if (prevx[posx[u]] == i) {
ans[u] += fw.sum(prevy[posy[u]]);
ans[u] -= fw.sum(nexty[posy[u]] + 1);
}
}
fw.upd(posy[xs[i].sc] + 1, 1);
for (auto& u : evs[i]) {
if (nextx[posx[u]] == i) {
ans[u] -= fw.sum(prevy[posy[u]]);
ans[u] += fw.sum(nexty[posy[u]] + 1);
}
}
}
f (i, 0, n) evs[i].clear();
f (i, 0, n) sm += ans[i] - 1;
if (sm / 2 >= k) R = M;
else L = M;
}
cout << R << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2806 ms |
43008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3318 ms |
42632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3318 ms |
42632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
