#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
using namespace std;
int pow(int a,int b,int m){int ans=1;while(b){if(b&1){ans=(ans*a)%m;}b>>=1;a=(a*a)%m;}return ans;}
int binpow(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a);}b>>=1;a=(a*a);}return ans;}
const int N = 1e5 + 2, inf = 1e9, MAXN = 3e5;
int k;
struct pt {
int x, y, id;
};
inline bool cmp_x (const pt & a, const pt & b) {
return a.x < b.x || a.x == b.x && a.y < b.y;
}
inline bool cmp_y (const pt & a, const pt & b) {
return a.y < b.y;
}
pt a[MAXN];
int mindist;
int ansa, ansb;
multiset <int> st;
inline void upd_ans (const pt & a, const pt & b) {
int dist = abs(a.x-b.x) + abs(a.y-b.y);
if((int)st.size() < k || *(--st.end()) > dist){
if((int)st.size() < k){
st.insert(dist);
}else{
st.erase(--st.end());
st.insert(dist);
}
}
}
void rec (int l, int r) {
if (r - l <= 3) {
for (int i=l; i<=r; ++i)
for (int j=i+1; j<=r; ++j)
upd_ans (a[i], a[j]);
sort (a+l, a+r+1, &cmp_y);
return;
}
int m = (l + r) >> 1;
int midx = a[m].x;
rec (l, m), rec (m+1, r);
static pt t[MAXN];
merge (a+l, a+m+1, a+m+1, a+r+1, t, &cmp_y);
copy (t, t+r-l+1, a+l);
int tsz = 0;
for (int i=l; i<=r; ++i)
if (abs (a[i].x - midx) < mindist) {
for (int j=tsz-1; j>=0 && a[i].y - t[j].y < mindist; --j)
upd_ans (a[i], t[j]);
t[tsz++] = a[i];
}
}
main(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> a[i].x >> a[i].y;
a[i].id = i;
}
sort (a, a+n, &cmp_x);
rec (0, n-1);
for(auto x : st){
cout << x <<"\n";
}
}
Compilation message
road_construction.cpp: In function 'bool cmp_x(const pt&, const pt&)':
road_construction.cpp:22:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
22 | return a.x < b.x || a.x == b.x && a.y < b.y;
| ~~~~~~~~~~~^~~~~~~~~~~~
road_construction.cpp: At global scope:
road_construction.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
71 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
26240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
13168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
13168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
