//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
//#undef LOCAL
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
if(b==0)return 1;
if(b==1)return(a%mod);
int tem=po(a,b/2);
if(b&1)return(((tem*tem)%mod)*a)%mod;
else return(tem*tem)%mod;
}
int GCD(int a,int b){
int x=0;
int ra,rb;
while(a&&b){
if(((a&1)==0)&&((b&1)==0)){
a>>=1,b>>=1,x++;
}
else if((a^b)&1){
if(a&1)b>>=1;
else a>>=1;
}
else{
ra=abs(a-b),rb=min(a,b);
a=ra,b=rb;
}
}
return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int n,k,ind=0,rd[250010];
pii pt[250010];
multiset<signed> st[250010];
struct TREAP{
int l,r,pr,v,c,si;
TREAP():l(-1),r(-1),pr(-1),v(-1),c(0),si(0){}
}treap[250010],treap1[250010];
void pull(int p){
int ss=treap[p].c;
if(treap[p].l!=-1)ss+=treap[treap[p].l].si;
if(treap[p].r!=-1)ss+=treap[treap[p].r].si;
treap[p].si=ss;
}
int merge(int a,int b){
if(a==-1||b==-1){
if(a==-1)return b;
else return a;
}
if(treap[a].pr>treap[b].pr){
treap[a].r=merge(treap[a].r,b);
pull(a);
return a;
}
else{
treap[b].l=merge(a,treap[b].l);
pull(b);
return b;
}
}
pii split(int a,int x){
if(a==-1)return{-1,-1};
if(treap[a].v<=x){
pii tp=split(treap[a].r,x);
treap[a].r=tp.X;
pull(a);
return {a,tp.Y};
}
else{
pii tp=split(treap[a].l,x);
treap[a].l=tp.Y;
pull(a);
return {tp.X,a};
}
}
int insert(int a,int x){
if(a==-1){
treap[ind].v=x;
treap[ind].c=treap[ind].si=1;
treap[ind].pr=rd[ind];
int pp=ind++;
return pp;
}
pii pt1=split(a,x);
pii pt2=split(pt1.X,x-1);
if(pt2.Y!=-1){
treap[pt2.Y].c++;
treap[pt2.Y].si=treap[pt2.Y].c;
return merge(merge(pt2.X,pt2.Y),pt1.Y);
}
else{
treap[ind].v=x;
treap[ind].c=treap[ind].si=1;
treap[ind].pr=rd[ind];
int re=merge(merge(pt2.X,ind),pt1.Y);
ind++;
return re;
}
}
int remove(int a,int x){
//bug(a,x);
pii pt1=split(a,x);
pii pt2=split(pt1.X,x-1);
if(treap[pt2.Y].si==1){
treap[pt2.Y].si--;
treap[pt2.Y].c--;
return merge(pt2.X,pt1.Y);
}
else{
//assert(treap[pt2.Y].si>1);
treap[pt2.Y].si--;
treap[pt2.Y].c--;
return merge(merge(pt2.X,pt2.Y),pt1.Y);
}
}
////////
vector<pii> v;
void pull1(int p){
int ss=treap1[p].c;
if(treap1[p].l!=-1)ss+=treap1[treap[p].l].si;
if(treap1[p].r!=-1)ss+=treap1[treap[p].r].si;
treap1[p].si=ss;
}
int merge1(int a,int b){
if(a==-1||b==-1){
if(a==-1)return b;
else return a;
}
if(treap1[a].pr>treap1[b].pr){
treap1[a].r=merge1(treap1[a].r,b);
pull1(a);
return a;
}
else{
treap1[b].l=merge1(a,treap1[b].l);
pull1(b);
return b;
}
}
pii split1(int a,int x){
if(a==-1)return{-1,-1};
if(treap1[a].v<=x){
pii tp=split1(treap1[a].r,x);
treap1[a].r=tp.X;
pull1(a);
return {a,tp.Y};
}
else{
pii tp=split1(treap1[a].l,x);
treap1[a].l=tp.Y;
pull1(a);
return {tp.X,a};
}
}
int insert1(int a,int x,int rx){
if(a==-1){
treap1[ind].v=x;
treap1[ind].c=treap1[ind].si=1;
treap1[ind].pr=rd[ind];
st[ind].insert(rx);
int pp=ind++;
return pp;
}
pii pt1=split1(a,x);
pii pt2=split1(pt1.X,x-1);
if(pt2.Y!=-1){
treap1[pt2.Y].c++;
treap1[pt2.Y].si=treap1[pt2.Y].c;
st[pt2.Y].insert(rx);
return merge1(merge1(pt2.X,pt2.Y),pt1.Y);
}
else{
treap1[ind].v=x;
treap1[ind].c=treap1[ind].si=1;
treap1[ind].pr=rd[ind];
st[ind].insert(rx);
int re=merge1(merge1(pt2.X,ind),pt1.Y);
ind++;
return re;
}
}
int remove1(int a,int x,int rx){
pii pt1=split1(a,x);
pii pt2=split1(pt1.X,x-1);
if(treap1[pt2.Y].si==1){
treap1[pt2.Y].c--;
treap1[pt2.Y].si--;
st[pt2.Y].erase(st[pt2.Y].find(rx));
return merge1(pt2.X,pt1.Y);
}
else{
assert(treap1[pt2.Y].si>1);
treap1[pt2.Y].si--;
treap1[pt2.Y].c--;
st[pt2.Y].erase(st[pt2.Y].find(rx));
return merge1(merge1(pt2.X,pt2.Y),pt1.Y);
}
}
void travel(int a){
if(a==-1)return;
travel(treap1[a].l);
//bug(treap1[a].v,treap1[a].c,sz(st[a]));
for(int i:st[a]){
v.pb({i,treap1[a].v});
}
travel(treap1[a].r);
}
////////
signed main(){
IOS();
freopen("05-01.txt","r",stdin);
cin>>n>>k;
F(n){
int x,y;
cin>>x>>y;
int xx,yy;
xx=x+y;
yy=x-y;
pt[i]={xx,yy};
}
sort(pt,pt+n);
F(250005)rd[i]=i;
random_shuffle(rd,rd+250004);
int rt=-1;
int l=0,r=4e9;
queue<pii> qu;
while(l<r){
int mi=(l+r)/2;
int s=0;
rt=-1,ind=0;
F(n){
while(!qu.empty()){
if(qu.front().X>=pt[i].X-mi)break;
rt=remove(rt,qu.front().Y);
qu.pop();
}
if(rt!=-1){
pii ppt=split(rt,pt[i].Y+mi);
pii ppt1=split(ppt.X,pt[i].Y-mi-1);
s+=treap[ppt1.Y].si;
//bug(treap[ppt1.Y].si,ppt1.Y);
rt=merge(merge(ppt1.X,ppt1.Y),ppt.Y);
}
rt=insert(rt,pt[i].Y);
qu.push(pt[i]);
}
//bug(mi,s);
while(!qu.empty()){
rt=remove(rt,qu.front().Y);
qu.pop();
}
if(s<k)l=mi+1;
else r=mi;
}
return 0;
int tk=l;
ind=0;
rt=-1;
while(!qu.empty())qu.pop();
multiset<int> sst;
F(n){
while(!qu.empty()){
if(qu.front().X>=pt[i].X-tk)break;
rt=remove1(rt,qu.front().Y,qu.front().X);
qu.pop();
}
if(rt!=-1){
pii ppt=split1(rt,pt[i].Y+tk);
pii ppt1=split1(ppt.X,pt[i].Y-tk-1);
v.clear();
travel(ppt1.Y);
//assert(sz(v)==treap1[ppt1.Y].si);
//bug(sz(v),treap1[ppt1.Y].si);
for(pii pi:v){
sst.insert(max(abs(pi.X-pt[i].X),abs(pi.Y-pt[i].Y)));
}
rt=merge1(merge1(ppt1.X,ppt1.Y),ppt.Y);
}
rt=insert1(rt,pt[i].Y,pt[i].X);
qu.push(pt[i]);
}
//bug(tk);
//F(n)bug(pt[i].X,pt[i].Y);
int cc=0;
for(int i:sst){
cc++;
cout<<i<<endl;
if(cc==k)break;
}
return 0;
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:264:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
264 | freopen("05-01.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
37452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
37452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
37548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
37548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
37452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
37452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
