#include<bits/stdc++.h>
using namespace std;
const int N = 25e4;
const int inf = 1e9;
mt19937 rng;
struct treap{
int l,r;
int x,y;
int val;
}v[N + 1];
struct point{
int x,y;
}v2[N];
int cnt = 1;
int lid,rid;
int n,k,cnt2 = 0;
int ans[N + 1];
void dbgtreap(int pos){
cout<<pos<<' '<<v[pos].l<<' '<<v[pos].r<<' '<<v[pos].x<<' '<<v[pos].y<<' '<<v[pos].val<<'\n';
if(v[pos].l != 0)dbgtreap(v[pos].l);
if(v[pos].r != 0)dbgtreap(v[pos].r);
}
int mergetreap(int l, int r){
if(l == 0){return r;}
if(r == 0){return l;}
if(v[l].y <= v[r].y){
v[r].l = mergetreap(l, v[r].l);
return r;
}else{
v[l].r = mergetreap(v[l].r, r);
return l;
}
}
void splittreap(int node, int nr, int nr2){
if(node == 0){
lid = 0;
rid = 0;
return;
}
if(v[node].x < nr || (v[node].x == nr && v[node].val <= nr2)){
splittreap(v[node].r, nr, nr2);
v[node].r = lid;
lid = node;
}else{
splittreap(v[node].l, nr, nr2);
v[node].l = rid;
rid = node;
}
}
int ins(int p, int x, int y, int val){
if(p == 0){
v[cnt] = {0,0,x,y,val};
cnt++;
return cnt - 1;
}
splittreap(p, x, val);
v[cnt] = {0,0,x,y,val};
p = mergetreap(lid, cnt);
p = mergetreap(p, rid);
cnt++;
return p;
}
int del(int p, int x, int val){
splittreap(p, x, val - 1);
int leftside = lid;
int rightside = rid;
splittreap(rid, x, val);
int id = mergetreap(leftside, rid);
return id;
}
void add(int pt,int x,int y){
if(pt == 0)return;
if(cnt2 > k)return;
ans[cnt2++] = max(abs(v[pt].x - y),abs(v[pt].val - x));
add(v[pt].l,x,y);
add(v[pt].r,x,y);
}
int get(int x){
cnt = 1;
cnt2 = 0;
int treapid = 0;
int pt = 0;
for(int i = 0;i < n;i++){
while(pt < i && v2[pt].x < v2[i].x - x){
treapid = del(treapid,v2[pt].y,v2[pt].x);
pt++;
}
splittreap(treapid,v2[i].y - x,-inf);
int p1 = lid;
splittreap(rid,v2[i].y + x + 1,-inf);
int p2 = lid;
int p3 = rid;
//dbgtreap(p2);
//cout<<"p2 "<<p2<<' '<<i<<' '<<x<<' '<<v2[i].x<<' '<<v2[i].y<<'\n';
add(p2,v2[i].x,v2[i].y);
treapid = mergetreap(p1,p2);
treapid = mergetreap(treapid,p3);
treapid = ins(treapid,v2[i].y,rand()%69420,v2[i].x);
if(cnt2 > k)return cnt2;
}
return cnt2;
}
int main(){
cin>>n>>k;
for(int i = 0;i < n;i++){
cin>>v2[i].x>>v2[i].y;
v2[i] = {v2[i].x + v2[i].y,v2[i].x - v2[i].y};
}
sort(v2,v2 + n,[&](point a,point b){
return a.x < b.x;
});
int l = 0,r = inf;
while(l != r){
int mij = (l + r)/2;
if(get(mij) <= k){
l = mij + 1;
}else r = mij;
}
get(l - 1);
sort(ans,ans + cnt2);
while(cnt2 < k){
ans[cnt2++] = l;
}
for(int i = 0;i < k;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
///i am losing my mind
Compilation message
road_construction.cpp: In function 'int del(int, int, int)':
road_construction.cpp:66:9: warning: unused variable 'rightside' [-Wunused-variable]
66 | int rightside = rid;
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
341 ms |
12368 KB |
Output is correct |
| 2 |
Correct |
344 ms |
12368 KB |
Output is correct |
| 3 |
Incorrect |
49 ms |
5000 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
12456 KB |
Output is correct |
| 2 |
Correct |
362 ms |
12112 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
12456 KB |
Output is correct |
| 2 |
Correct |
362 ms |
12112 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
