#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 250000 + 6;
ll X[N], Y[N];
int p[N];
int n, k, x[N], y[N];
vector<ll>xs,ys;
int F[N];
void upd(int pos, int v) {
while (pos < N) {
F[pos] += v;
pos |= pos + 1;
}
}
int get(int pos) {
int r = 0;
while (pos >= 0) {
r += F[pos];
pos &= pos + 1, pos--;
}
return r;
}
bool check(ll M) {
int res = 0;
int l = 1;
for (int i = 0 ; i < N ; ++ i) F[i] = 0;
for (int i = 1 ; i <= n ; ++ i) {
while (l < i && X[p[i]] - X[p[l]] >= M) {
upd(y[p[l]], -1);
l++;
}
int sx = lower_bound(ys.begin(), ys.end(), Y[p[i]] - M + 1) - ys.begin();
int ex = upper_bound(ys.begin(), ys.end(), Y[p[i]] + M - 1) - ys.begin() - 1;
res += get(ex) - get(sx - 1);
if (res >= k) break;
upd(y[p[i]], +1);
}
while (l <= n) upd(y[p[l]], -1), ++l;
return res >= k;
}
vector<ll>ANS;
void restore(ll M) {
set<pair<ll,ll>>S = {{Y[p[1]], X[p[1]]}};
int l = 1;
for (int i = 2 ; i <= n ; ++ i) {
while (l < i && X[p[i]] - X[p[l]] >= M) {
S.erase({Y[p[l]], X[p[l]]});
l++;
}
auto st = S.lower_bound(pair{Y[p[i]] - M + 1, -1e10});
for (; st != S.end() ; ++ st) {
if (max(abs(st->first - Y[p[i]]), abs(st->second - X[p[i]])) < M) {
ANS.emplace_back(max(abs(st->first - Y[p[i]]), abs(st->second - X[p[i]])));
} else break;
}
S.insert({Y[p[i]], X[p[i]]});
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1 ; i <= n ; ++ i) {
ll a, b;
cin >> a >> b;
X[i] = a + b, Y[i] = a - b;
xs.emplace_back(X[i]), ys.emplace_back(Y[i]);
}
sort(xs.begin(), xs.end()); xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
sort(ys.begin(), ys.end()); ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
for (int i = 1 ; i <= n ; ++ i) {
x[i] = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
y[i] = lower_bound(ys.begin(), ys.end(), Y[i]) - ys.begin();
}
for (int i = 1 ; i <= n ; ++ i) {
p[i] = i;
}
sort(p + 1, p + 1 + n, [](int i, int j) {
return X[i] < X[j];
});
ll L = 1, R = ll(1e10);
ll ans = -1;
while (L <= R) {
ll M = (L + R) / 2;
int res = check(M);
if (!res) { // ? < k
ans = M;
L = M + 1;
} else {
R = M - 1;
}
}
assert(ans != -1);
restore(ans);
sort(ANS.begin(), ANS.end());
for (ll i : ANS) cout << i << endl;;
int cnt = ANS.size();
for (; cnt < k ; ++cnt) {
cout << ans << "\n";
}
cout << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
579 ms |
6380 KB |
Output is correct |
2 |
Correct |
584 ms |
6252 KB |
Output is correct |
3 |
Correct |
586 ms |
6220 KB |
Output is correct |
4 |
Correct |
583 ms |
6252 KB |
Output is correct |
5 |
Correct |
572 ms |
4972 KB |
Output is correct |
6 |
Correct |
9 ms |
1388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2059 ms |
18620 KB |
Output is correct |
2 |
Correct |
1936 ms |
18636 KB |
Output is correct |
3 |
Correct |
580 ms |
6244 KB |
Output is correct |
4 |
Correct |
1752 ms |
18340 KB |
Output is correct |
5 |
Correct |
1718 ms |
18580 KB |
Output is correct |
6 |
Correct |
1685 ms |
18420 KB |
Output is correct |
7 |
Correct |
1468 ms |
18384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1844 ms |
17360 KB |
Output is correct |
2 |
Correct |
2271 ms |
17488 KB |
Output is correct |
3 |
Correct |
6 ms |
1388 KB |
Output is correct |
4 |
Correct |
859 ms |
15348 KB |
Output is correct |
5 |
Correct |
1220 ms |
17616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1844 ms |
17360 KB |
Output is correct |
2 |
Correct |
2271 ms |
17488 KB |
Output is correct |
3 |
Correct |
6 ms |
1388 KB |
Output is correct |
4 |
Correct |
859 ms |
15348 KB |
Output is correct |
5 |
Correct |
1220 ms |
17616 KB |
Output is correct |
6 |
Correct |
2740 ms |
17360 KB |
Output is correct |
7 |
Correct |
2669 ms |
17436 KB |
Output is correct |
8 |
Correct |
6 ms |
1536 KB |
Output is correct |
9 |
Correct |
6 ms |
1388 KB |
Output is correct |
10 |
Correct |
2699 ms |
17488 KB |
Output is correct |
11 |
Correct |
937 ms |
15312 KB |
Output is correct |
12 |
Correct |
1296 ms |
17684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
579 ms |
6380 KB |
Output is correct |
2 |
Correct |
584 ms |
6252 KB |
Output is correct |
3 |
Correct |
586 ms |
6220 KB |
Output is correct |
4 |
Correct |
583 ms |
6252 KB |
Output is correct |
5 |
Correct |
572 ms |
4972 KB |
Output is correct |
6 |
Correct |
9 ms |
1388 KB |
Output is correct |
7 |
Correct |
1784 ms |
11884 KB |
Output is correct |
8 |
Correct |
1719 ms |
11884 KB |
Output is correct |
9 |
Correct |
572 ms |
6292 KB |
Output is correct |
10 |
Correct |
1539 ms |
11124 KB |
Output is correct |
11 |
Correct |
1274 ms |
11240 KB |
Output is correct |
12 |
Correct |
563 ms |
9944 KB |
Output is correct |
13 |
Correct |
1006 ms |
10504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
579 ms |
6380 KB |
Output is correct |
2 |
Correct |
584 ms |
6252 KB |
Output is correct |
3 |
Correct |
586 ms |
6220 KB |
Output is correct |
4 |
Correct |
583 ms |
6252 KB |
Output is correct |
5 |
Correct |
572 ms |
4972 KB |
Output is correct |
6 |
Correct |
9 ms |
1388 KB |
Output is correct |
7 |
Correct |
2059 ms |
18620 KB |
Output is correct |
8 |
Correct |
1936 ms |
18636 KB |
Output is correct |
9 |
Correct |
580 ms |
6244 KB |
Output is correct |
10 |
Correct |
1752 ms |
18340 KB |
Output is correct |
11 |
Correct |
1718 ms |
18580 KB |
Output is correct |
12 |
Correct |
1685 ms |
18420 KB |
Output is correct |
13 |
Correct |
1468 ms |
18384 KB |
Output is correct |
14 |
Correct |
1844 ms |
17360 KB |
Output is correct |
15 |
Correct |
2271 ms |
17488 KB |
Output is correct |
16 |
Correct |
6 ms |
1388 KB |
Output is correct |
17 |
Correct |
859 ms |
15348 KB |
Output is correct |
18 |
Correct |
1220 ms |
17616 KB |
Output is correct |
19 |
Correct |
2740 ms |
17360 KB |
Output is correct |
20 |
Correct |
2669 ms |
17436 KB |
Output is correct |
21 |
Correct |
6 ms |
1536 KB |
Output is correct |
22 |
Correct |
6 ms |
1388 KB |
Output is correct |
23 |
Correct |
2699 ms |
17488 KB |
Output is correct |
24 |
Correct |
937 ms |
15312 KB |
Output is correct |
25 |
Correct |
1296 ms |
17684 KB |
Output is correct |
26 |
Correct |
1784 ms |
11884 KB |
Output is correct |
27 |
Correct |
1719 ms |
11884 KB |
Output is correct |
28 |
Correct |
572 ms |
6292 KB |
Output is correct |
29 |
Correct |
1539 ms |
11124 KB |
Output is correct |
30 |
Correct |
1274 ms |
11240 KB |
Output is correct |
31 |
Correct |
563 ms |
9944 KB |
Output is correct |
32 |
Correct |
1006 ms |
10504 KB |
Output is correct |
33 |
Correct |
4634 ms |
21348 KB |
Output is correct |
34 |
Correct |
4579 ms |
21468 KB |
Output is correct |
35 |
Correct |
3929 ms |
20664 KB |
Output is correct |
36 |
Correct |
1558 ms |
19396 KB |
Output is correct |
37 |
Correct |
1442 ms |
19448 KB |
Output is correct |
38 |
Correct |
1839 ms |
20560 KB |
Output is correct |