#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
struct Persist{
int seg[8000000],lc[8000000],rc[8000000];
ll ptr=1;
ll build(ll l, ll r){
if(l==r){
seg[ptr]=1e18,lc[ptr]=rc[ptr]=-1; ptr++; return ptr-1;
}
else{
ll mid=(l+r)>>1;
ll curptr=ptr; ptr++;
lc[curptr]=build(l,mid); rc[curptr]=build(mid+1,r);
seg[curptr]=1e18;
return curptr;
}
}
ll upd(ll ul, ll l, ll r, ll val, ll id){
if(l==r){
seg[ptr]=val; lc[ptr]=rc[ptr]=-1; ptr++; return ptr-1;
}
else{
ll mid=(l+r)>>1;
ll curp=ptr; ptr++;
if(ul<=mid){
lc[curp]=upd(ul,l,mid,val,lc[id]); rc[curp]=rc[id];
}
else{
rc[curp]=upd(ul,mid+1,r,val,rc[id]); lc[curp]=lc[id];
}
seg[curp]=min(seg[lc[curp]],seg[rc[curp]]);
return curp;
}
}
ll qry(ll ql, ll qr, ll l, ll r, ll id){
if(ql>qr)return 1e18;
if(l>qr||r<ql)return 1e18;
if(l>=ql&&r<=qr){
return seg[id];
}
ll mid=(l+r)>>1;
return min(qry(ql,qr,l,mid,lc[id]),qry(ql,qr,mid+1,r,rc[id]));
}
ll bs(ll l, ll r, ll k, ll id){
if(l==r)return l;
ll mid=(l+r)>>1;
if(seg[lc[id]]==k)return bs(l,mid,k,lc[id]);
return bs(mid+1,r,k,rc[id]);
}
ll find(ll ql, ll qr, ll l, ll r, ll id, ll k){
if(ql>qr)return -1;
if(l>qr||r<ql)return -1;
if(l>=ql&&r<=qr){
if(seg[id]!=k) return -1;
return bs(l,r,k,id);
}
ll mid=(l+r)>>1;
ll bruh=find(ql,qr,l,mid,lc[id],k);
if(bruh!=-1)return bruh;
bruh=find(ql,qr,mid+1,r,rc[id],k);
return bruh;
}
}st,st2;
struct THING{
ll val,verx,very,insegpos;
bool operator<(const THING& th)const{
return val>th.val;
}
};
priority_queue<THING>pq;
int version[250005][3];
int prevver,prevver2;
vector<pair<ll,ll> >disc;
ll pos(pair<ll,ll>x){
return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;
}
int32_t main(){
ll n,k;
cin>>n>>k;
ll x[n+5],y[n+5];
for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
vector<pair<ll,ll> >pts;
for(int i=1;i<=n;i++)pts.push_back({x[i],y[i]});
sort(pts.begin(),pts.end());
for(int i=0;i<pts.size();i++){
disc.push_back({pts[i].second,i});
}
sort(disc.begin(),disc.end());
prevver=st.build(1,disc.size()); prevver2=st2.build(1,disc.size());
for(int i=0;i<pts.size();i++){
int xx=pts[i].first,yy=pts[i].second;
version[i][1]=prevver; version[i][2]=prevver2;
prevver=st.upd(pos(make_pair(yy,i)),1,disc.size(),-xx-yy,prevver);
prevver2=st2.upd(pos(make_pair(yy,i)),1,disc.size(),-xx+yy,prevver2);
}
for(int i=0;i<pts.size();i++){
int xx=pts[i].first,yy=pts[i].second;
ll posi=pos(make_pair(yy,i));
ll for1=st.qry(1,posi,1,disc.size(),version[i][1]);
ll segtreebst=st.find(1,posi,1,disc.size(),version[i][1],for1);
pq.push({for1+xx+yy,i,1,segtreebst});
ll for2=st2.qry(posi+1,disc.size(),1,disc.size(),version[i][2]);
segtreebst=st2.find(posi+1,disc.size(),1,disc.size(),version[i][2],for2);
pq.push({for2+xx-yy,i,2,segtreebst});
}
for(int i=1;i<=k;i++){
THING lol=pq.top();
ll val=lol.val,verx=lol.verx,very=lol.very,insegpos=lol.insegpos;
ll xx=pts[verx].first,yy=pts[verx].second;
pq.pop();
cout<<val<<'\n';
ll posi=pos(make_pair(yy,i));
if(very==1){
version[verx][very]=st.upd(insegpos,1,disc.size(),1e18,version[verx][very]);
ll for1=st.qry(1,posi,1,disc.size(),version[verx][1]);
ll segtreebst=st.find(1,posi,1,disc.size(),version[verx][1],for1);
pq.push({for1+xx+yy,verx,1,segtreebst});
}
else{
version[verx][very]=st2.upd(insegpos,1,disc.size(),1e18,version[verx][very]);
ll for2=st2.qry(posi+1,disc.size(),1,disc.size(),version[verx][2]);
ll segtreebst=st2.find(posi+1,disc.size(),1,disc.size(),version[verx][2],for2);
pq.push({for2+xx-yy,verx,2,segtreebst});
}
}
}
Compilation message
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:88:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i=0;i<pts.size();i++){
| ~^~~~~~~~~~~
road_construction.cpp:93:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=0;i<pts.size();i++){
| ~^~~~~~~~~~~
road_construction.cpp:99:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i=0;i<pts.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
185 ms |
83016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1200 ms |
709000 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1332 ms |
291364 KB |
Output is correct |
| 2 |
Correct |
1293 ms |
291600 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 4 |
Correct |
428 ms |
289360 KB |
Output is correct |
| 5 |
Correct |
746 ms |
291800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1332 ms |
291364 KB |
Output is correct |
| 2 |
Correct |
1293 ms |
291600 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 4 |
Correct |
428 ms |
289360 KB |
Output is correct |
| 5 |
Correct |
746 ms |
291800 KB |
Output is correct |
| 6 |
Correct |
1329 ms |
291420 KB |
Output is correct |
| 7 |
Correct |
1360 ms |
291480 KB |
Output is correct |
| 8 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
12624 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
185 ms |
83016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
185 ms |
83016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
