#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=1e10;
ll n,k,ymax;
map<int,int> nrm;
map<pii,int> where;
set<pii> setik;
struct point
{
ll x,y;
} v[250005];
bool byx(point a,point b)
{
return a.x<b.x;
}
vector<int> vals;
vector<int> myx[250005];
struct node
{
node *l,*r;
ll st,dr;
ll x,y,minim;
node()
{
l=NULL;
r=NULL;
x=0;
y=0;
minim=0;
st=0;
dr=0;
}
};
node *arb[2][2][200005]; /// [xmic,xmare][ymic,ymare]
struct answer
{
ll x,y,minim;
};
node *build(int st,int dr)
{
node *rez=new node;
rez->st=st;
rez->dr=dr;
rez->minim=INF;
rez->x=INF;
rez->y=INF;
if(st==dr)
return rez;
int mij=(st+dr)/2;
rez->l=build(st,mij);
rez->r=build(mij+1,dr);
return rez;
}
node *update(node *me,int poz,ll x,ll y,ll val)
{
ll st=me->st;
ll dr=me->dr;
node *rez=new node;
rez->st=st;
rez->dr=dr;
rez->l=me->l;
rez->r=me->r;
if(st==dr)
{
rez->x=x;
rez->y=y;
rez->minim=val;
return rez;
}
ll mij=(st+dr)/2;
if(poz<=mij)
rez->l=update(rez->l,poz,x,y,val);
else
rez->r=update(rez->r,poz,x,y,val);
rez->minim=rez->l->minim;
rez->x=rez->l->x;
rez->y=rez->l->y;
if(rez->r->minim<rez->minim)
{
rez->minim=rez->r->minim;
rez->x=rez->r->x;
rez->y=rez->r->y;
}
return rez;
}
answer query(node *me,int a,int b)
{
ll st=me->st;
ll dr=me->dr;
if(st>=a&&dr<=b)
return {me->x,me->y,me->minim};
answer rez={INF,INF,INF};
ll mij=(st+dr)/2;
if(a<=mij)
{
answer p=query(me->l,a,b);
if(p.minim<rez.minim)
rez=p;
}
if(b>mij)
{
answer p=query(me->r,a,b);
if(p.minim<rez.minim)
rez=p;
}
return rez;
}
node* add(node *me,ll x,ll y,ll a,ll b)
{
ll poz=nrm[y];
answer rez=query(me,poz,poz);
ll val=0;
if(a==0)
val-=x;
else
val+=x;
if(b==0)
val-=y;
else
val+=y;
if(val<rez.minim)
me=update(me,poz,x,y,val);
return me;
}
node* out(node *me,ll x,ll y,ll a,ll b)
{
ll poz=nrm[y];
answer rez=query(me,poz,poz);
if(rez.x!=x||rez.y!=y)
return me;
ll nxt=INF;
if(a==0)
{
ll st=0;
ll dr=myx[poz].size();
dr--;
while(st<=dr)
{
ll mij=(st+dr)/2;
if(myx[poz][mij]<x)
{
nxt=myx[poz][mij];
st=mij+1;
}
else
dr=mij-1;
}
}
else
{
ll st=0;
ll dr=myx[poz].size();
dr--;
while(st<=dr)
{
ll mij=(st+dr)/2;
if(myx[poz][mij]>x)
{
nxt=myx[poz][mij];
dr=mij-1;
}
else
st=mij+1;
}
}
if(nxt==INF)
me=update(me,poz,INF,INF,INF);
else
{
ll val=0;
x=nxt;
if(a==0)
val-=x;
else
val+=x;
if(b==0)
val-=y;
else
val+=y;
me=update(me,poz,x,y,val);
}
return me;
}
answer getmin(ll ind)
{
answer rez={INF,INF,INF};
ll x=v[ind].x,y=v[ind].y;
ll poz=nrm[y];
answer a=query(arb[0][0][ind],1,poz);
a.minim+=x+y;
if(a.minim<rez.minim)
rez=a;
a=query(arb[0][1][ind],poz,ymax);
a.minim+=x-y;
if(a.minim<rez.minim)
rez=a;
a=query(arb[1][0][ind],1,poz);
a.minim+=(-x+y);
if(a.minim<rez.minim)
rez=a;
a=query(arb[1][1][ind],poz,ymax);
a.minim+=(-x-y);
if(a.minim<rez.minim)
rez=a;
return rez;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
vals.push_back(v[i].y);
}
vector<ll> sol;
if(k==n*(n-1)/2)
{
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
sol.push_back(abs(v[i].x-v[j].x)+abs(v[i].y-v[j].y));
sort(sol.begin(),sol.end());
for(auto i:sol)
cout<<i<<'\n';
return 0;
}
sort(v+1,v+n+1,byx);
for(int i=1;i<=n;i++)
where[{v[i].x,v[i].y}]=i;
sort(vals.begin(),vals.end());
vals.erase(unique(vals.begin(),vals.end()),vals.end());
for(int i=0;i<vals.size();i++)
{
nrm[vals[i]]=i+1;
ymax=i+1;
}
for(int i=1;i<=n;i++)
myx[nrm[v[i].y]].push_back(v[i].x);
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
arb[i][j][1]=build(1,ymax);
for(int i=2;i<=n;i++)
{
arb[1][0][1]=add(arb[1][0][1],v[i].x,v[i].y,1,0);
arb[1][1][1]=add(arb[1][1][1],v[i].x,v[i].y,1,1);
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<=1;j++)
for(int p=0;p<=1;p++)
arb[j][p][i]=arb[j][p][i-1];
arb[1][0][i]=out(arb[1][0][i],v[i].x,v[i].y,1,0);
arb[1][1][i]=out(arb[1][1][i],v[i].x,v[i].y,1,1);
arb[0][0][i]=add(arb[0][0][i],v[i-1].x,v[i-1].y,0,0);
arb[0][1][i]=add(arb[0][1][i],v[i-1].x,v[i-1].y,0,1);
}
for(int i=1;i<=n;i++)
{
ll val=getmin(i).minim;
setik.insert({val,i});
}
k*=2;
while(k--)
{
ll i=(*setik.begin()).second;
setik.erase(setik.begin());
answer a=getmin(i);
sol.push_back(a.minim);
ll val=a.minim;
ll x=a.x;
ll y=a.y;
if(where[{x,y}]<i)
{
arb[0][0][i]=out(arb[0][0][i],x,y,0,0);
arb[0][1][i]=out(arb[0][1][i],x,y,0,1);
}
else
{
arb[1][0][i]=out(arb[1][0][i],x,y,1,0);
arb[1][1][i]=out(arb[1][1][i],x,y,1,1);
}
a=getmin(i);
if(a.minim<=2e9)
setik.insert({a.minim,i});
}
for(int i=0;i<sol.size();i+=2)
cout<<sol[i]<<'\n';
return 0;
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:236:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
236 | for(int i=0;i<vals.size();i++)
| ~^~~~~~~~~~~~
road_construction.cpp:273:12: warning: unused variable 'val' [-Wunused-variable]
273 | ll val=a.minim;
| ^~~
road_construction.cpp:290:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
290 | for(int i=0;i<sol.size();i+=2)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2805 ms |
711444 KB |
Output is correct |
| 2 |
Correct |
2729 ms |
711300 KB |
Output is correct |
| 3 |
Correct |
35 ms |
13268 KB |
Output is correct |
| 4 |
Correct |
34 ms |
13252 KB |
Output is correct |
| 5 |
Correct |
2452 ms |
710252 KB |
Output is correct |
| 6 |
Correct |
11 ms |
18264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
239 ms |
173428 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5636 ms |
1974656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5636 ms |
1974656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2805 ms |
711444 KB |
Output is correct |
| 2 |
Correct |
2729 ms |
711300 KB |
Output is correct |
| 3 |
Correct |
35 ms |
13268 KB |
Output is correct |
| 4 |
Correct |
34 ms |
13252 KB |
Output is correct |
| 5 |
Correct |
2452 ms |
710252 KB |
Output is correct |
| 6 |
Correct |
11 ms |
18264 KB |
Output is correct |
| 7 |
Correct |
9060 ms |
1864580 KB |
Output is correct |
| 8 |
Correct |
8801 ms |
1864348 KB |
Output is correct |
| 9 |
Correct |
36 ms |
13256 KB |
Output is correct |
| 10 |
Correct |
5163 ms |
1778040 KB |
Output is correct |
| 11 |
Correct |
6428 ms |
1739636 KB |
Output is correct |
| 12 |
Correct |
1688 ms |
946068 KB |
Output is correct |
| 13 |
Correct |
1903 ms |
883348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2805 ms |
711444 KB |
Output is correct |
| 2 |
Correct |
2729 ms |
711300 KB |
Output is correct |
| 3 |
Correct |
35 ms |
13268 KB |
Output is correct |
| 4 |
Correct |
34 ms |
13252 KB |
Output is correct |
| 5 |
Correct |
2452 ms |
710252 KB |
Output is correct |
| 6 |
Correct |
11 ms |
18264 KB |
Output is correct |
| 7 |
Runtime error |
239 ms |
173428 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
