#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxA = 1e10;
const int maxN = 3e5;
pair<ll, ll> p[maxN], q[maxN];
vector<pair<ll, ll>> cY[maxN];
struct Fenwick {
int tree[maxN];
void reset(){
fill(tree, tree+maxN, 0);
}
void update(int pos, int val){
pos++;
while(pos < maxN){
tree[pos] += val;
pos += pos&(-pos);
}
}
int query(int pos){
pos++;
int ans = 0;
while(pos > 0){
ans += tree[pos];
pos -= pos&(-pos);
}
return ans;
}
int query(int l, int r){
if(l > r) return 0;
return query(r) - query(l-1);
}
} fenwick;
struct SegmentTree {
set<pair<ll, ll>> tree[4*maxN];
void reset(){
for(int x=0;x<4*maxN;x++){
tree[x].clear();
}
}
void update(int v, int curL, int curR, int pos, ll val1, ll val2){
if(curL > curR) return;
if(curL == curR){
tree[v].insert({val1, val2});
return;
}
int curM = (curL+curR) >> 1;
tree[v].insert({val1, val2});
if(pos <= curM) update(2*v+1, curL, curM, pos, val1, val2);
else update(2*v+2, curM+1, curR, pos, val1, val2);
}
void query(int v, int curL, int curR, int l, int r, ll mx, ll cur, vector<ll> &ans){
if(curL > curR || l > r) return;
if(curL == l && curR == r){
for(auto p : tree[v]){
if(p.first > mx) break;
ans.push_back(cur-p.second);
}
return;
}
int curM = (curL+curR) >> 1;
query(2*v+1, curL, curM, l, min(curM, r), mx, cur, ans);
query(2*v+2, curM+1, curR, max(l, curM+1), r, mx, cur, ans);
}
} tree;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("input.txt","r",stdin);
int n, k;
cin >> n >> k;
for(int x=0;x<n;x++){
cin >> p[x].first >> p[x].second;
p[x] = {p[x].first+p[x].second, p[x].first-p[x].second};
}
ll max_d = 0;
{
vector<ll> val;
for(int x=0;x<n;x++){
val.push_back(p[x].second);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
ll left = 1, right = maxA;
while(left <= right){ // log(N.logN.logMaxA)
ll mid = (left+right) >> 1;
tree.reset();
vector<array<ll, 4>> v;
for(int x=0;x<n;x++){
int idx = lower_bound(val.begin(), val.end(), p[x].second-mid) - val.begin();
int idx2 = lower_bound(val.begin(), val.end(), p[x].second+mid + 1) - val.begin();
v.push_back({p[x].first-mid-1, x+1, idx, idx2});
v.push_back({p[x].first+mid, x+1, idx, idx2});
v.push_back({p[x].first, 0, lower_bound(val.begin(), val.end(), p[x].second) - val.begin(), x});
}
sort(v.begin(), v.end());
ll sum = 0;
for(auto a : v){
if(a[1] == 0){
fenwick.update(a[2], 1);
} else {
if(p[a[1]-1].first <= a[0]){
sum += fenwick.query(a[2], a[3]-1) - 1;
} else {
sum -= fenwick.query(a[2], a[3]-1);
}
}
}
if(sum >= 2*k){
max_d = mid;
right = mid-1;
} else {
left = mid+1;
}
}
}
vector<ll> vX, vY;
for(int x=0;x<n;x++){
vX.push_back(p[x].first);
vY.push_back(p[x].second);
}
sort(vX.begin(), vX.end());
sort(vY.begin(), vY.end());
vX.erase(unique(vX.begin(), vX.end()), vX.end());
vY.erase(unique(vY.begin(), vY.end()), vY.end());
for(int x=0;x<n;x++){
q[x] = {lower_bound(vX.begin(), vX.end(), p[x].first) - vX.begin(), lower_bound(vY.begin(), vY.end(), p[x].second) - vY.begin()};
swap(q[x].first, q[x].second);
}
sort(q, q+n, [&](pair<ll, ll> a, pair<ll, ll> b) -> bool {
if(a.first == b.first){
return a.second < b.second;
}
return a.first > b.first;
});
vector<ll> ans;
auto solve = [&](pair<ll, ll> pts[], ll max_d) -> void {
tree.reset();
int pos = 0, pos2 = 0;
for(int x=0;x<n;x++){
int left = 0, right = pts[x].second;
int bound = pts[x].second;
while(left <= right){
int mid = (left+right) >> 1;
if(vX[pts[x].second]-vX[mid] <= max_d){
bound = mid;
right = mid-1;
} else {
left = mid+1;
}
}
int old = ans.size();
tree.query(0, 0, vX.size()-1, bound, pts[x].second, vY[pts[x].first]+vX[pts[x].second], vX[pts[x].second], ans);
tree.update(0, 0, vX.size()-1, pts[x].second, vY[pts[x].first]+vX[pts[x].second], vX[pts[x].second]);
}
};
solve(q, max_d-1);
vX.clear();
vY.clear();
for(int x=0;x<n;x++){
p[x] = {p[x].second, -p[x].first};
}
for(int x=0;x<n;x++){
vX.push_back(p[x].first);
vY.push_back(p[x].second);
}
sort(vX.begin(), vX.end());
sort(vY.begin(), vY.end());
vX.erase(unique(vX.begin(), vX.end()), vX.end());
vY.erase(unique(vY.begin(), vY.end()), vY.end());
for(int x=0;x<n;x++){
q[x] = {lower_bound(vX.begin(), vX.end(), p[x].first) - vX.begin(), lower_bound(vY.begin(), vY.end(), p[x].second) - vY.begin()};
swap(q[x].first, q[x].second);
}
sort(q, q+n, [&](pair<ll, ll> a, pair<ll, ll> b) -> bool {
if(a.first == b.first){
return a.second < b.second;
}
return a.first > b.first;
});
solve(q, max_d-1);
sort(ans.begin(), ans.end());
while(ans.size() < k){
ans.push_back(max_d);
}
for(auto val : ans){
cout << val << "\n";
}
return 0;
}
Compilation message
road_construction.cpp: In lambda function:
road_construction.cpp:191:8: warning: unused variable 'old' [-Wunused-variable]
191 | int old = ans.size();
| ^~~
road_construction.cpp:176:7: warning: unused variable 'pos' [-Wunused-variable]
176 | int pos = 0, pos2 = 0;
| ^~~
road_construction.cpp:176:16: warning: unused variable 'pos2' [-Wunused-variable]
176 | int pos = 0, pos2 = 0;
| ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:229:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
229 | while(ans.size() < k){
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
69256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10096 ms |
376600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10091 ms |
314636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10091 ms |
314636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
69256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
69256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
