#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=2e9+5;
const ll INFBIG=5e9;
int n,k,ymax;
map<int,int> nrm;
map<pii,int> where;
set<pair<long long,int>> setik;
int nrop=0;
struct point
{
int 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;
int st,dr;
int x1,y1;
int x2,y2;
long long minim1,minim2;
node()
{
l=NULL;
r=NULL;
x1=0;
y1=0;
minim1=0;
x2=0;
y2=0;
minim2=0;
st=0;
dr=0;
}
};
node *arb[2][250005]; /// [xmic,xmare][ymic,ymare]
struct answer
{
int x,y;
long long minim;
};
node *build(int st,int dr)
{
node *rez=new node;
rez->st=st;
rez->dr=dr;
rez->minim1=INFBIG;
rez->x1=INF;
rez->y1=INF;
rez->x2=INF;
rez->y2=INF;
rez->minim2=INFBIG;
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,int x1,int y1,ll val1,int x2,int y2,ll val2)
{
int st=me->st;
int 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->x1=x1;
rez->y1=y1;
rez->minim1=val1;
rez->x2=x2;
rez->y2=y2;
rez->minim2=val2;
return rez;
}
int mij=(st+dr)/2;
if(poz<=mij)
rez->l=update(rez->l,poz,x1,y1,val1,x2,y2,val2);
else
rez->r=update(rez->r,poz,x1,y1,val1,x2,y2,val2);
rez->minim1=rez->l->minim1;
rez->x1=rez->l->x1;
rez->y1=rez->l->y1;
if(rez->r->minim1<rez->minim1)
{
rez->minim1=rez->r->minim1;
rez->x1=rez->r->x1;
rez->y1=rez->r->y1;
}
rez->minim2=rez->l->minim2;
rez->x2=rez->l->x2;
rez->y2=rez->l->y2;
if(rez->r->minim2<rez->minim2)
{
rez->minim2=rez->r->minim2;
rez->x2=rez->r->x2;
rez->y2=rez->r->y2;
}
return rez;
}
answer query(node *me,int a,int b,int who)
{
int st=me->st;
int dr=me->dr;
if(st>=a&&dr<=b)
{
if(who==1)
return {me->x1,me->y1,me->minim1};
if(who==2)
return {me->x2,me->y2,me->minim2};
}
answer rez={INF,INF,INFBIG};
int mij=(st+dr)/2;
if(a<=mij)
{
answer p=query(me->l,a,b,who);
if(p.minim<rez.minim)
rez=p;
}
if(b>mij)
{
answer p=query(me->r,a,b,who);
if(p.minim<rez.minim)
rez=p;
}
return rez;
}
node* add(node *me,int x,int y,int a)
{
int poz=nrm[y];
answer rez=query(me,poz,poz,1);
int x1=rez.x,y1=rez.y;
ll minim1=rez.minim;
rez=query(me,poz,poz,2);
int x2=rez.x,y2=rez.y;
ll minim2=rez.minim;
ll val=0;
if(a==0)
val-=x;
else
val+=x;
/// b==0
val-=y;
if(val<minim1)
{
x1=x;
y1=y;
minim1=val;
}
val=0;
if(a==0)
val-=x;
else
val+=x;
/// b==1
val+=y;
if(val<minim2)
{
x2=x;
y2=y;
minim2=val;
}
me=update(me,poz,x1,y1,minim1,x2,y2,minim2);
return me;
}
node* out(node *me,int x,int y,int a)
{
bool found=0;
int poz=nrm[y];
answer rez=query(me,poz,poz,1);
ll x1=rez.x;
ll y1=rez.y;
ll minim1=rez.minim;
int b=0;
if(rez.x==x&&rez.y==y)
{
found=1;
int nxt=INF;
if(a==0)
{
int st=0;
int dr=myx[poz].size();
dr--;
while(st<=dr)
{
int mij=(st+dr)/2;
if(myx[poz][mij]<x)
{
nxt=myx[poz][mij];
st=mij+1;
}
else
dr=mij-1;
}
}
else
{
int st=0;
int dr=myx[poz].size();
dr--;
while(st<=dr)
{
int mij=(st+dr)/2;
if(myx[poz][mij]>x)
{
nxt=myx[poz][mij];
dr=mij-1;
}
else
st=mij+1;
}
}
if(nxt==INF)
{
x1=INF;
y1=INF;
minim1=INFBIG;
}
else
{
ll val=0;
x1=nxt;
if(a==0)
val-=x;
else
val+=x;
if(b==0)
val-=y;
else
val+=y;
y1=y;
minim1=val;
}
}
rez=query(me,poz,poz,2);
ll x2=rez.x;
ll y2=rez.y;
ll minim2=rez.minim;
b=1;
if(rez.x==x&&rez.y==y)
{
found=1;
int nxt=INF;
if(a==0)
{
int st=0;
int dr=myx[poz].size();
dr--;
while(st<=dr)
{
int mij=(st+dr)/2;
if(myx[poz][mij]<x)
{
nxt=myx[poz][mij];
st=mij+1;
}
else
dr=mij-1;
}
}
else
{
int st=0;
int dr=myx[poz].size();
dr--;
while(st<=dr)
{
int mij=(st+dr)/2;
if(myx[poz][mij]>x)
{
nxt=myx[poz][mij];
dr=mij-1;
}
else
st=mij+1;
}
}
if(nxt==INF)
{
x2=INF;
y2=INF;
minim2=INFBIG;
}
else
{
ll val=0;
x2=nxt;
if(a==0)
val-=x;
else
val+=x;
if(b==0)
val-=y;
else
val+=y;
y2=y;
minim2=val;
}
}
if(!found)
return me;
me=update(me,poz,x1,y1,minim1,x2,y2,minim2);
return me;
}
answer getmin(int ind)
{
answer rez={INF,INF,INFBIG};
int x=v[ind].x,y=v[ind].y;
int poz=nrm[y];
answer a=query(arb[0][ind],1,poz,1);
a.minim+=x+y;
if(a.minim<rez.minim)
rez=a;
a=query(arb[0][ind],poz,ymax,2);
a.minim+=x-y;
if(a.minim<rez.minim)
rez=a;
a=query(arb[1][ind],1,poz,1);
a.minim+=(-x+y);
if(a.minim<rez.minim)
rez=a;
a=query(arb[1][ind],poz,ymax,2);
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<long long> 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)*1LL+1LL*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++)
arb[i][1]=build(1,ymax);
for(int i=2;i<=n;i++)
arb[1][1]=add(arb[1][1],v[i].x,v[i].y,1);
for(int i=2;i<=n;i++)
{
for(int j=0;j<=1;j++)
arb[j][i]=arb[j][i-1];
arb[1][i]=out(arb[1][i],v[i].x,v[i].y,1);
arb[0][i]=add(arb[0][i],v[i-1].x,v[i-1].y,0);
}
for(int i=1;i<=n;i++)
{
long long val=getmin(i).minim;
setik.insert({val,i});
}
while(k--)
{
nrop++;
int i=(*setik.begin()).second;
setik.erase(setik.begin());
answer a=getmin(i);
sol.push_back(a.minim);
long long val=a.minim;
int x=a.x;
int y=a.y;
int j=where[{x,y}];
if(j<i)
{
arb[0][i]=out(arb[0][i],x,y,0);
answer b=getmin(j);
setik.erase({b.minim,j});
arb[1][j]=out(arb[1][j],v[i].x,v[i].y,1);
b=getmin(j);
setik.insert({b.minim,j});
}
else
{
arb[1][i]=out(arb[1][i],x,y,1);
answer b=getmin(j);
setik.erase({b.minim,j});
arb[0][j]=out(arb[0][j],v[i].x,v[i].y,0);
b=getmin(j);
setik.insert({b.minim,j});
}
a=getmin(i);
setik.insert({a.minim,i});
}
for(int i=0;i<sol.size();i++)
cout<<sol[i]<<'\n';
return 0;
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:367:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
367 | for(int i=0;i<vals.size();i++)
| ~^~~~~~~~~~~~
road_construction.cpp:397:19: warning: unused variable 'val' [-Wunused-variable]
397 | long long val=a.minim;
| ^~~
road_construction.cpp:424:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
424 | for(int i=0;i<sol.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1820 ms |
361648 KB |
Output is correct |
| 2 |
Correct |
1769 ms |
361732 KB |
Output is correct |
| 3 |
Correct |
33 ms |
13252 KB |
Output is correct |
| 4 |
Correct |
34 ms |
13348 KB |
Output is correct |
| 5 |
Incorrect |
1660 ms |
360216 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
603 ms |
126112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3579 ms |
1016576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3579 ms |
1016576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1820 ms |
361648 KB |
Output is correct |
| 2 |
Correct |
1769 ms |
361732 KB |
Output is correct |
| 3 |
Correct |
33 ms |
13252 KB |
Output is correct |
| 4 |
Correct |
34 ms |
13348 KB |
Output is correct |
| 5 |
Incorrect |
1660 ms |
360216 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1820 ms |
361648 KB |
Output is correct |
| 2 |
Correct |
1769 ms |
361732 KB |
Output is correct |
| 3 |
Correct |
33 ms |
13252 KB |
Output is correct |
| 4 |
Correct |
34 ms |
13348 KB |
Output is correct |
| 5 |
Incorrect |
1660 ms |
360216 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
