#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, INF = 1e10 + 10;
int n, k;
pair<int, int> a[maxn];
int ysz;
vector<int> xvals = {-INF}, yvals = {-INF};
int ldc(int x) {return lower_bound(yvals.begin(), yvals.end(), x) - yvals.begin();}
int rdc(int x) {return upper_bound(yvals.begin(), yvals.end(), x) - yvals.begin() - 1;}
int fen[maxn];
void update(int id) {
while (id <= ysz) {
fen[id]++;
id += (id & -id);
}
}
int qry(int id) {
int val = 0;
while (id >= 1) {
val += fen[id];
id -= (id & -id);
}
return val;
}
int cunt(int dist) {
int ans = 0, pt = 0;
for (int i=1;i<=n;i++) {
while (pt+1 <= n && a[pt+1].first <= a[i].first + dist) {
pt++;
int L = ldc(a[pt].second - dist), R = rdc(a[pt].second + dist);
ans -= qry(R) - qry(L-1);
// cout << "- " << (a[pt].first+a[pt].second)/2 << " " << (a[pt].first-a[pt].second)/2 << " " << qry(R) - qry(L-1) << endl;
}
int L = ldc(a[i].second - dist), R = rdc(a[i].second + dist);
ans += qry(R) - qry(L-1);
// cout << "+ " << (a[i].first+a[i].second)/2 << " " << (a[i].first-a[i].second)/2 << " " << qry(R) - qry(L-1) << endl;
int pos = ldc(a[i].second);
update(pos);
}
return ans;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for (int i=1;i<=n;i++) {
int x, y;
cin >> x >> y;
a[i] = {x+y, x-y};
xvals.push_back(x+y);
yvals.push_back(x-y);
}
sort(a+1, a+n+1);
sort(xvals.begin(), xvals.end());
xvals.erase(unique(xvals.begin(), xvals.end()), xvals.end());
sort(yvals.begin(), yvals.end());
yvals.erase(unique(yvals.begin(), yvals.end()), yvals.end());
ysz = yvals.size() - 1;
int L = 1, R = INF;
while (L < R) {
int mid = (L+R)/2;
if (cunt(mid) < k) L = mid+1;
else R = mid;
}
int dist = L - 1;
vector<int> ans;
multiset<pair<int,int>> s;
s.insert({INF, INF});
for (int i=1;i<=n;i++) s.insert({a[i].second, a[i].first});
int l = 0, r = 0;
int cnt = 0;
for (int i=1;i<=n;i++) {
// while (r+1 <= n && a[r+1].first <= a[i].first + dist) {
// r++;
// s.insert({a[r].second, a[r].first});
// }
// while (l+1 <= n && a[l+1].first < a[i].first - dist) {
// l++;
// s.erase({a[l].second, a[l].first});
// }
// cout << "test\n";
// cout << (a[i].first+a[i].second)/2 << " " << (a[i].first-a[i].second)/2 << endl;
// auto it = s.lower_bound({a[i].second - dist, -INF});
// while ((it->first) <= a[i].second + dist) {
// pair<int,int> cur = *it;
// if (a[i].first!=cur.second || a[i].second!=cur.first) {
// ans.push_back(max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)));
// // assert(max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)) <= dist);
// cnt++;
// // cout << max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)) << endl;
// }
// it++;
// }
for (auto [x, y]:s) {
if ((a[i].second!=x || a[i].first!=y) && abs(a[i].second - x) <= dist && abs(a[i].first - y) <= dist) {
ans.push_back(max(abs(a[i].first - y), abs(a[i].second - x)));
}
}
}
while (ans.size() < 2*k) ans.push_back(L);
sort(ans.begin(), ans.end());
for (int i=0;i<2*k;i+=2) cout << ans[i] << '\n';
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:107:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
107 | while (ans.size() < 2*k) ans.push_back(L);
| ~~~~~~~~~~~^~~~~
road_construction.cpp:75:9: warning: unused variable 'l' [-Wunused-variable]
75 | int l = 0, r = 0;
| ^
road_construction.cpp:75:16: warning: unused variable 'r' [-Wunused-variable]
75 | int l = 0, r = 0;
| ^
road_construction.cpp:76:9: warning: unused variable 'cnt' [-Wunused-variable]
76 | int cnt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
9400 KB |
Output is correct |
| 2 |
Correct |
62 ms |
9396 KB |
Output is correct |
| 3 |
Correct |
54 ms |
9392 KB |
Output is correct |
| 4 |
Correct |
58 ms |
9392 KB |
Output is correct |
| 5 |
Correct |
55 ms |
8896 KB |
Output is correct |
| 6 |
Correct |
9 ms |
2640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10061 ms |
26208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10045 ms |
26016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10045 ms |
26016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
9400 KB |
Output is correct |
| 2 |
Correct |
62 ms |
9396 KB |
Output is correct |
| 3 |
Correct |
54 ms |
9392 KB |
Output is correct |
| 4 |
Correct |
58 ms |
9392 KB |
Output is correct |
| 5 |
Correct |
55 ms |
8896 KB |
Output is correct |
| 6 |
Correct |
9 ms |
2640 KB |
Output is correct |
| 7 |
Execution timed out |
10033 ms |
12824 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
9400 KB |
Output is correct |
| 2 |
Correct |
62 ms |
9396 KB |
Output is correct |
| 3 |
Correct |
54 ms |
9392 KB |
Output is correct |
| 4 |
Correct |
58 ms |
9392 KB |
Output is correct |
| 5 |
Correct |
55 ms |
8896 KB |
Output is correct |
| 6 |
Correct |
9 ms |
2640 KB |
Output is correct |
| 7 |
Execution timed out |
10061 ms |
26208 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
