#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 x,y;
long long minim;
node()
{
l=NULL;
r=NULL;
x=0;
y=0;
minim=0;
st=0;
dr=0;
}
};
node *arb[2][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->minim=INFBIG;
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,int x,int y,ll val)
{
int st=me->st;
int dr=me->dr;
node *rez;
if(nrop<=1e5)
rez=new node;
else
rez=me;
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;
}
int 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)
{
int st=me->st;
int dr=me->dr;
if(st>=a&&dr<=b)
return {me->x,me->y,me->minim};
answer rez={INF,INF,INFBIG};
int 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,int x,int y,int a,int b)
{
int 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,int x,int y,int a,int b)
{
int poz=nrm[y];
answer rez=query(me,poz,poz);
if(rez.x!=x||rez.y!=y)
return me;
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)
me=update(me,poz,INF,INF,INFBIG);
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(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][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<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++)
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++)
{
long long val=getmin(i).minim;
setik.insert({val,i});
}
k*=2;
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;
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);
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:244:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
244 | for(int i=0;i<vals.size();i++)
| ~^~~~~~~~~~~~
road_construction.cpp:282:19: warning: unused variable 'val' [-Wunused-variable]
282 | long long val=a.minim;
| ^~~
road_construction.cpp:298:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
298 | for(int i=0;i<sol.size();i+=2)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
747 ms |
128032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1463 ms |
113776 KB |
Output is correct |
| 2 |
Correct |
1506 ms |
113772 KB |
Output is correct |
| 3 |
Correct |
35 ms |
13260 KB |
Output is correct |
| 4 |
Correct |
463 ms |
113680 KB |
Output is correct |
| 5 |
Correct |
471 ms |
113792 KB |
Output is correct |
| 6 |
Correct |
463 ms |
110840 KB |
Output is correct |
| 7 |
Correct |
496 ms |
111432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5346 ms |
1502012 KB |
Output is correct |
| 2 |
Correct |
5485 ms |
1502004 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
235 ms |
99164 KB |
Output is correct |
| 5 |
Correct |
1155 ms |
523740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5346 ms |
1502012 KB |
Output is correct |
| 2 |
Correct |
5485 ms |
1502004 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
235 ms |
99164 KB |
Output is correct |
| 5 |
Correct |
1155 ms |
523740 KB |
Output is correct |
| 6 |
Correct |
5472 ms |
1502040 KB |
Output is correct |
| 7 |
Correct |
5509 ms |
1501920 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 9 |
Correct |
3 ms |
8540 KB |
Output is correct |
| 10 |
Correct |
5344 ms |
1428040 KB |
Output is correct |
| 11 |
Correct |
235 ms |
99032 KB |
Output is correct |
| 12 |
Correct |
1177 ms |
524784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
747 ms |
128032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
747 ms |
128032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
