#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define f first
#define s second
#define mp make_pair
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
const ll MAXN=250100;
const ll MAXK=19;
ll N,K,a,b;
vpi V;
vi res;
vector<pair<pi,ll>> A;
vpi ans;
ll W,M;
struct node{
ll v;
node *l,*r;
node(){
v=0;
l=r=nullptr;
}
void upd(ll s,ll e,ll x,ll va){
if(s==e){
// cerr<<"Upd "<<x<<' '<<va<<'\n';
v+=va;return;
}
ll m=(ll)(s+e)/2;
// cerr<<s<<' '<<m<<' '<<e<<'\n';
if(x<=m){
if(!l)l=new node();
l->upd(s,m,x,va);
}
else{
if(!r)r=new node();
r->upd(m+1,e,x,va);
}
v=0;
if(l)v+=l->v;
if(r)v+=r->v;
}
ll query(ll s,ll e,ll x,ll y){
ll m=(ll)(s+e)/2;
if(s==x&&e==y){
return v;
}
if(y<=m){
if(!l)return 0;
return l->query(s,m,x,y);
}else if(x>m){
if(!r)return 0;
return r->query(m+1,e,x,y);
}else{
ll ans=0;
if(l)ans+=l->query(s,m,x,m);
if(r)ans+=r->query(m+1,e,m+1,y);
return ans;
}
}
}*root;
struct node2{
node2 *l,*r;
set<ll> S;
node2(){
l=r=nullptr;
S.clear();
}
void upd(ll s,ll e,ll x,ll va,ll flag){
++W;
if(flag==1)S.insert(va);
else S.erase(va);
if(s==e)return;
ll m=(ll)(s+e)/2;
if(x<=m){
if(!l)l=new node2();
l->upd(s,m,x,va,flag);
}
else{
if(!r)r=new node2();
r->upd(m+1,e,x,va,flag);
}
}
void query(ll s,ll e,ll x,ll y,ll k){
ll m=(ll)(s+e)/2;
if(s==x&&e==y){
// if(SZ(S))cerr<<SZ(S)<<'\n';
for(auto i:S){
if(i<k){
ans.pb(k,i);
}else break;
}
return;
}
if(y<=m){
if(!l)return;
return l->query(s,m,x,y,k);
}else if(x>m){
if(!r)return;
return r->query(m+1,e,x,y,k);
}else{
if(l)l->query(s,m,x,m,k);
if(r)r->query(m+1,e,m+1,y,k);
}
}
}*root2;
ll cnt(ll d){
if(d<0)return 0;
// root=new node();
// cerr<<"HI\n";
ll s=-1;
ll e=-1;
ll ans=0;
for(auto i:A){
ll ep=i.f.f+d;
ll sp=i.f.f-d;
while(e+1<N&&A[e+1].f.f<=ep){
++e;
root->upd((ll)0,(ll)10e9,(ll)5e9+A[e].f.s,1);
}
while(s+1<N&&A[s+1].f.f<sp){
++s;
root->upd((ll)0,(ll)10e9,(ll)5e9+A[s].f.s,-1);
}
ll t=root->query((ll)0,(ll)10e9,i.f.s-d+5e9,i.f.s+d+5e9);
// cerr<<s<<' '<<e<<' '<<t<<'\n';
ans+=t;
if((ans-N)/2>=K)return 1;
}
while(s+1<N){++s;root->upd((ll)0,(ll)10e9,A[s].f.s,-1);}
return 0;
}
void generate(ll d){
ll s=-1;
ll e=-1;
for(auto i:A){
ll ep=i.f.f+d;
ll sp=i.f.f-d;
while(e+1<N&&A[e+1].f.f<=ep){++e;root2->upd((ll)0,(ll)10e9,5e9+A[e].f.s,A[e].s,1);}
while(s+1<N&&A[s+1].f.f<sp){++s;root2->upd((ll)0,(ll)10e9,5e9+A[s].f.s,A[s].s,0);}
root2->query((ll)0,(ll)10e9,5e9+i.f.s-d,i.f.s+d+5e9,i.s);
}
}
ll d(ll a,ll b){
return abs(V[a].f-V[b].f) + abs(V[a].s-V[b].s);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
root=new node();
root2=new node2();
cin>>N>>K;
for(ll i=0;i<N;++i){
cin>>a>>b;
V.pb(a,b);
A.pb(mp(b-a,b+a),i);
}
sort(ALL(A));
ll l=0;
ll u=4e9;
while(u-l>0){
ll m=(l+u)/2;
if(cnt(m))u=m;
else l=m+1;
}
--l;
generate(l);
// cout<<W<<' '<<M<<'\n';
for(auto i:ans){
res.pb(d(i.f,i.s));
}
// assert(SZ(res)<K);
sort(ALL(res));
while(SZ(res)<K)res.pb(l+1);
// assert(SZ(res)==K);
// cerr<<SZ(res)<<'\n';
for(auto i:res){
cout<<i<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
8116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5230 ms |
804816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6309 ms |
765828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6309 ms |
765828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
8116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
8116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
