#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,int>> 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==-1e9&&e==3e9){
// cerr<<"Upd "<<x<<' '<<va<<'\n';
// }
if(s==e){
// cerr<<"Upd "<<x<<' '<<va<<'\n';
v+=va;return;
}
ll m=(ll)(s+e+2e9)/2-1e9;
// 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)(2e9+s+e)/2-1e9;
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<int> S;
node2(){
l=r=nullptr;
S.clear();
}
void upd(ll s,ll e,ll x,ll va,ll flag){
++W;
if(flag)S.insert(va);
else S.erase(va);
if(s==e)return;
ll m=(ll)(s+e+2e9)/2-1e9;
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)(2e9+s+e)/2-1e9;
if(s==x&&e==y){
M+=SZ(S);
if(M>K)assert(0);
// if(SZ(S))cerr<<SZ(S)<<'\n';
for(auto i:S){
if(k<i){
ans.pb(k,i);
}
}
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){
// 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(-1e9,(ll)3e9,A[e].f.s,1);}
while(s+1<N&&A[s+1].f.f<sp){++s;root->upd(-1e9,(ll)3e9,A[s].f.s,-1);}
ll t=root->query(-1e9,(ll)3e9,i.f.s-d,i.f.s+d);
ans+=t;
}
while(s+1<N){++s;root->upd(-1e9,(ll)3e9,A[s].f.s,-1);}
return (ans-N)/2;
}
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(-1e9,(ll)3e9,A[e].f.s,A[e].s,1);}
while(s+1<N&&A[s+1].f.f<sp){++s;root2->upd(-1e9,(ll)3e9,A[s].f.s,A[s].s,0);}
root2->query(-1e9,(ll)3e9,i.f.s-d,i.f.s+d,i.s);
}
}
ll d(int a,int 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=2e9;
while(u-l>0){
ll m=(l+u)/2;
ll k=cnt(m);
if(k>=K)u=m;
else l=m+1;
}
assert(SZ(ans)<K);
--l;
generate(l);
// cout<<W<<' '<<M<<'\n';
for(auto i:ans){
res.pb(d(i.f,i.s));
}
sort(ALL(res));
while(SZ(res)<K)res.pb(l+1);
for(auto i:res){
cout<<i<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
11652 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10107 ms |
120536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10072 ms |
110624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10072 ms |
110624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
11652 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
11652 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
