#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define int long long
typedef tree<pair<int,int>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset;
orderedset seg[1000000];
vector<pair<int,int>> points;
vector<pair<int,int>> edges;
int n;
void build(int x=1,int L=1,int R=n){
if(L==R){
seg[x].insert({points[L].second,L});
return;
}
int mid = (L+R)/2;
build(2*x,L,mid);
build(2*x+1,mid+1,R);
for(auto i:seg[2*x])seg[x].insert(i);
for(auto i:seg[2*x+1])seg[x].insert(i);
}
int get(int qL,int qR,int qUpper,int qLower,int x=1,int L=1,int R=n){
if(qR<L or R<qL)return 0;
if(qL<=L and R<=qR){
return seg[x].order_of_key({qUpper+1,0})-seg[x].order_of_key({qLower,0});
}
int mid = (L+R)/2;
return get(qL,qR,qUpper,qLower,2*x,L,mid)+get(qL,qR,qUpper,qLower,2*x+1,mid+1,R);
}
int base;
void rec(int qL,int qR,int qUpper,int qLower,int x=1,int L=1,int R=n){
if(qR<L or R<qL)return;
if(qL<=L and R<=qR){
auto lo = seg[x].order_of_key({qLower,0});
auto hi = seg[x].order_of_key({qUpper+1,0});
while(lo!=hi){
edges.emplace_back(min(base,(int)seg[x].find_by_order(lo)->second),max(base,(int)seg[x].find_by_order(lo)->second));
lo++;
}
return;
}
int mid = (L+R)/2;
rec(qL,qR,qUpper,qLower,2*x,L,mid);
rec(qL,qR,qUpper,qLower,2*x+1,mid+1,R);
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> n >> k;
for(int i=1;i<=n;i++){
int x,y;
cin >> x >> y;
points.emplace_back(x-y,x+y);
}
sort(points.begin(),points.end());
points.insert(points.begin(),{0,0});
build();
auto calc = [&](int limit){
int curr = 0;
for(int i=1;i<=n;i++){
int qL = lower_bound(points.begin()+1,points.end(),make_pair(points[i].first-limit,(int)-1e15))-points.begin();
int qR = lower_bound(points.begin()+1,points.end(),make_pair(points[i].first+limit,(int)-1e15))-points.begin()-1;
curr+=get(qL,qR,points[i].second+limit,points[i].second-limit);
if(curr>=2*k)return false;
}
curr-=n;
return curr<2*k;
};
vector<int> edgewt;
auto recover = [&](int limit){
for(int i=1;i<=n;i++){
int qL = lower_bound(points.begin(),points.end(),make_pair(points[i].first-limit,(int)-1e15))-points.begin();
int qR = lower_bound(points.begin(),points.end(),make_pair(points[i].first+limit,(int)-1e15))-points.begin()-1;
base = i;
rec(qL,qR,points[i].second+limit,points[i].second-limit);
}
sort(edges.begin(),edges.end());
edges.erase(unique(edges.begin(),edges.end()),edges.end());
for(auto[a,b]:edges){
if(a==b)continue;
edgewt.emplace_back(max(abs(points[a].first-points[b].first),abs(points[a].second-points[b].second)));
}
sort(edgewt.begin(),edgewt.end());
};
int ans = 0;
#pragma GCC unroll 40
for(int jump=2147483648ll;jump;jump/=2)if(calc(ans+jump))ans+=jump;
recover(ans);
for(int i=0;i<k;i++){
if(i<edgewt.size())cout<<edgewt[i]<<'\n';
else cout<<ans+1<<'\n';
}
}
Compilation message
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:102:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if(i<edgewt.size())cout<<edgewt[i]<<'\n';
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
109488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1983 ms |
409092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1085 ms |
400056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1085 ms |
400056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
109488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
109488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
