// #pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=5e5;
bool vs[N+5];
int n,k,ans[N+5];
vector <int> answer;
vector <pair<int,int>> p;
struct Fenwick_Tree_virtual{
int FT[N+5];
vector <int> v;
void clear(){
v.clear();
for (int i=1;i<=N;++i) FT[i]=0;
}
void Add(int x){
v.push_back(x);
}
void Build(){
sort(v.begin(),v.end());
}
void Update(int idx, int val){
idx=lower_bound(v.begin(),v.end(),idx)-v.begin()+1;
for (;idx<=N;idx+=idx&(-idx)) FT[idx]+=val;
}
int Get(int idx){
int val=0;
idx=lower_bound(v.begin(),v.end(),idx)-v.begin()+1;
for (;idx;idx-=idx&(-idx)) val+=FT[idx];
return val;
}
int Sum(int l, int r){
return Get(r)-Get(l-1);
}
} ft;
int Check(int x){
ft.clear();
for (int i=1;i<=n;++i){
ans[i]=0;
vs[i]=false;
ft.Add(p[i].second);
}
vector <pair<int,int>> st;
for (int i=1;i<=n;++i){
st.push_back({p[i].first-x-1,i});
st.push_back({p[i].first+x,i});
ft.Add(p[i].second-x-1);
ft.Add(p[i].second+x);
}
ft.Build();
sort(st.begin(),st.end());
int pointer=0;
for (int i=0;i<st.size();++i){
while (pointer<n && p[pointer+1].first<=st[i].first){
++pointer;
ft.Update(p[pointer].second,1);
}
if (!vs[st[i].second]){
vs[st[i].second]=true;
ans[st[i].second]-=ft.Sum(p[st[i].second].second-x,p[st[i].second].second+x);
}
else ans[st[i].second]+=ft.Sum(p[st[i].second].second-x,p[st[i].second].second+x);
}
int now=0;
for (int i=1;i<=n;++i) now+=ans[i]-1;
return now/2;
}
int kc(int a, int b, int c, int d){
// cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<max(abs(a-c),abs(b-d))<<"\n";
return max(abs(a-c),abs(b-d));
}
void trace(int x){
multiset <int> s;
vector <pair<int,int>> st=p;
st.erase(st.begin());
int pointer=0,pointer1=1;
map <int,multiset<int>> mp;
for (pair <int,int> t : st){
while (pointer<n && p[pointer+1].first<=t.first+x){
++pointer;
s.insert(p[pointer].second);
mp[p[pointer].second].insert(p[pointer].first);
// cout<<p[pointer].second<<' '<<p[pointer].first<<"\n";
}
while (pointer1<=n && p[pointer1].first<t.first-x){
s.erase(s.find(p[pointer1].second));
mp[p[pointer1].second].erase(mp[p[pointer1].second].find(p[pointer1].first));
++pointer1;
}
auto it=s.lower_bound(t.second-x);
if (it==s.end()) continue;
while (*it<=t.second+x){
for (int val : mp[*it]) answer.push_back(kc(val,*it,t.first,t.second));
while (*next(it)==*it){
it=next(it);
if (it==s.end()) break;
}
if (it==s.end()) break;
it=next(it);
if (it==s.end()) break;
}
}
// cout<<"\n";
}
void Solve(){
cin>>n>>k;
for (int i=1;i<=n;++i){
int u,v;
cin>>u>>v;
p.push_back({u+v,u-v});
}
p.push_back({-1e18,-1e18});
sort(p.begin(),p.end());
int l=0,r=4e9;
while (l<r){
int md=l+r>>1;
if (Check(md)>=k) r=md;
else l=md+1;
}
// cout<<l<<"\n";
// for (int i=1;i<=n;++i) cout<<p[i].first<<' '<<p[i].second<<"\n";
// cout<<"\n";
trace(l-1);
vector <int> as=answer;
answer.clear();
// for (int x : as) cout<<x<<" ";
// cout<<"\n";
map <int,int> cnt;
for (int x : as){
if (!x){
++cnt[x];
if (cnt[x]>n) answer.push_back(x);
}
else{
++cnt[x];
if (cnt[x]&1) answer.push_back(x);
}
}
while (answer.size()<k) answer.push_back(l);
sort(answer.begin(),answer.end());
for (int x : answer) cout<<x<<"\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (fopen("file.inp","r")){
freopen ("file.inp","r",stdin);
freopen ("file.out","w",stdout);
}
int t=1;
// cin>>t;
while (t--) Solve();
cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC <<"ms.";
}
Compilation message
library.cpp: In function 'long long int Check(long long int)':
library.cpp:55:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i=0;i<st.size();++i){
| ~^~~~~~~~~~
library.cpp: In function 'void Solve()':
library.cpp:118:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
118 | int md=l+r>>1;
| ~^~
library.cpp:141:25: 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]
141 | while (answer.size()<k) answer.push_back(l);
| ~~~~~~~~~~~~~^~
library.cpp: In function 'int main()':
library.cpp:149:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | freopen ("file.inp","r",stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:150:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | freopen ("file.out","w",stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc0naqxX.o: in function `main':
library.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccRAht4W.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccRAht4W.o: in function `main':
grader.cpp:(.text.startup+0x25): undefined reference to `Solve(int)'
collect2: error: ld returned 1 exit status
