#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()
template<class S, class T>
bool chmin(S &a, const T &b) {
return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 998244353;
int n, k;
vector<int> x, y;
int dist(int i, int j) {
return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}
auto get(int l, int r) {
multiset<int> ret;
if (l >= r) return ret;
int mid = (l + r) / 2;
multiset<int> L = get(l, mid - 1);
multiset<int> R = get(mid + 1, r);
for (int i = l; i <= r; ++i) {
if (i == mid) continue;
ret.insert(dist(i, mid));
if (size(ret) > k) ret.erase(--ret.end());
}
for (int i = l; i < mid; ++i) {
for (int j = mid + 1; j <= r; ++j) {
ret.insert(dist(i, j));
if (size(ret) > k) ret.erase(--ret.end());
}
}
for (int i : L) {
ret.insert(i);
if (size(ret) > k) ret.erase(--ret.end());
}
for (int i : R) {
ret.insert(i);
if (size(ret) > k) ret.erase(--ret.end());
}
return ret;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> k;
x.resize(n), y.resize(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
}
vector<pair<int, int>> v;
for (int i = 0; i < n; ++i) {
v.emplace_back(x[i], y[i]);
}
sort(all(v));
for (int i = 0; i < n; ++i) {
x[i] = v[i].first, y[i] = v[i].second;
}
multiset<int> res = get(0, n - 1);
for (int i : res) {
cout << i << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
