#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
//#define int ll
//const int MAXS = 4500000;
//int S[MAXS];
struct node {
int sm;
node* l = nullptr, *r = nullptr;
node() = default;
node(int sm_) {
sm = sm_;
}
};
node* upd(node* root, int tl, int tr, int p, int val) {
if (tl + 1 == tr) {
node *nw = new node(root->sm + val);
return nw;
}
node* nw = new node(0);
int tm = (tl + tr) / 2;
if (p < tm) {
if (root->l == nullptr) {
node* nwl = new node(0);
root->l = nwl;
}
auto rs = upd(root->l, tl, tm, p, val);
nw->l = rs;
nw->r = root->r;
nw->sm = rs->sm;
if (nw->r != nullptr) nw->sm += nw->r->sm;
}
else {
if (root->r == nullptr) {
root->r = new node(0);
}
auto rs = upd(root->r, tm, tr, p, val);
nw->l = root->l;
nw->r = rs;
nw->sm = rs->sm;
if (nw->l != nullptr) nw->sm += nw->l->sm;
}
return nw;
}
int get(node* root, int tl, int tr, int l, int r) {
if (root == nullptr) return 0;
if (l <= tl && tr <= r) return root->sm;
if (tr <= l || tl >= r) return 0;
int tm = (tl + tr) / 2;
return get(root->l, tl, tm, l, r) + get(root->r, tm, tr, l, r);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k; cin >> n >> k;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) cin >> a[i].ff >> a[i].sc;
vector<pair<int, int>> 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));
vector<node*> roots(n + 1);
roots[0] = new node(0);
f (i, 0, n) {
posy[ys[i].sc] = i;
}
for (int i = 0; i < n; i++) {
roots[i + 1] = upd(roots[i], 0, n, posy[i], 1);
}
auto getrect = [&](ll lx, ll rx, ll ly, ll ry) {
int li, ri, lj, rj;
{
int L = -1, R = n;
while (R - L > 1) {
int M = (L + R) / 2;
if (xs[M].ff >= lx) R = M;
else L = M;
}
li = R;
}
{
int L = -1, R = n;
while (R - L > 1) {
int M = (L + R) / 2;
if (xs[M].ff <= rx) L = M;
else R = M;
}
ri = L;
}
{
int L = -1, R = n;
while (R - L > 1) {
int M = (L + R) / 2;
if (ys[M].ff <= ry) L = M;
else R = M;
}
rj = L;
}
{
int L = -1, R = n;
while (R - L > 1) {
int M = (L + R) / 2;
if (ys[M].ff >= ly) R = M;
else L = M;
}
lj = R;
}
return get(roots[ri + 1], 0, n, lj, rj + 1) - get(roots[li], 0, n, lj, rj + 1);
};
ll L = -1, R = 4000000000ll;
while (R - L > 1) {
ll M = (L + R) / 2;
ll sm = 0;
for (int i = 0; i < n; i++) {
sm += getrect(b[i].ff - M, b[i].ff + M, b[i].sc - M, b[i].sc + M) - 1;
}
if (sm / 2 >= k) R = M;
else L = M;
}
cout << R << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10038 ms |
175956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10026 ms |
175956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10026 ms |
175956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
