#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;
vector<pair<pi,int>> A;
vpi ans;
struct node{
ll v;
node *l,*r;
node(){
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;
}
}
void res(){
v=0;
if(l)l->res();
if(r)r->res();
}
}*root;
struct node2{
node2 *l,*r;
set<int> S;
node2(){
l=r=nullptr;
}
void upd(ll s,ll e,ll x,ll va,ll flag){
// if(s==-1e9&&e==3e9){
// if(flag)cerr<<"ADD ";
// else cerr<<"RMV ";
// cerr<<x<<' '<<va<<'\n';
// }
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){
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){
root->res();
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;
}
return (ans-N)/2;
}
void generate(ll d){
ll s=-1;
ll e=-1;
ll ans=0;
for(auto i:A){
// cerr<<i.f.f<<' '<<i.f.s<<' '<<i.s<<'\n';
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(){
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);
}
// for(auto i:A){
// cerr<<i.f<<' '<<i.s<<'\n';
// }
sort(ALL(A));
ll l=0;
ll u=2e9;
// for(ll i=3;i<=7;++i){
// cerr<<cnt(i)<<'\n';
// }
// return 0;
while(u-l>0){
ll m=(l+u)/2;
ll k=cnt(m);
if(k>=K)u=m;
else l=m+1;
}
--l;
generate(l);
vi res;
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';
}
}
Compilation message
road_construction.cpp: In function 'void generate(ll)':
road_construction.cpp:143:8: warning: unused variable 'ans' [-Wunused-variable]
143 | ll ans=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
12952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10104 ms |
123392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10009 ms |
115796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10009 ms |
115796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
12952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
12952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
