This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
const int inf = 4e9 + 42;
int n, k;
vector<pii > points;
inline int new_x(pii a) {
return a.fi - a.se;
}
inline int new_y(pii a) {
return a.fi + a.se;
}
inline int dist(pii a, pii b) {
return abs(a.fi - b.fi) + abs(a.se - b.se);
}
bool cmp_1(pii a, pii b) {
if(new_x(a) == new_x(b)) {
return (a.fi < b.fi);
}
return new_x(a) < new_x(b);
}
struct cmp_2 {
bool operator()(const pii &a, const pii &b) {
if(new_y(a) == new_y(b)) {
return (a.se < b.se);
}
return new_y(a) < new_y(b);
}
};
vector<int> real_ans;
bool check(int l) {
set<pii, cmp_2> s;
vector<int> ans;
int idx_2 = 0;
for(int idx_1 = 0; idx_1 < n; idx_1++) {
while(idx_2 < idx_1 && (new_x(points[idx_1]) - new_x(points[idx_2])) > l) {
s.erase(s.find(points[idx_2]));
idx_2++;
}
pii cur = points[idx_1];
auto it = s.lower_bound(mp(cur.fi, cur.se - l));
while(it != s.end()) {
pii nei = *it;
int d = dist(cur, nei);
if(d <= l) {
ans.pb(d);
if((int) ans.size() >= k + 1) {
return false;
}
} else {
break;
}
it++;
}
s.insert(cur);
}
real_ans = ans;
return true;
}
void solve() {
cin >> n >> k;
points.assign(n, mp(0, 0));
for(int i = 0; i < n; i++) {
cin >> points[i].fi >> points[i].se;
}
sort(points.begin(), points.end(), cmp_1);
#ifdef __DEBUG__
for(pii p : points) {
cout << p.fi << " " << p.se << "\n";
}
#endif
int l = 1, r = inf;
while(l < r - 1) {
int mid = (l + r) / 2;
if(check(mid)) {
l = mid;
} else {
r = mid;
}
}
#ifdef __DEBUG__
cout << l << "\n";
cout << "-----\n";
#endif
check(l);
sort(real_ans.begin(), real_ans.end());
real_ans.resize(k, r);
for(int cur : real_ans) {
cout << cur << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |