| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1080268 | kustizus | Library (JOI18_library) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #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.";
}