#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,k,b[750005],x[750005],y[750005];
unordered_map<ll,ll>M1,M2;
vector<ll>beg[750005],er[750005];
vector<ll>A;
multiset<pair<ll,ll> >st;
multiset<pair<ll,ll>>::iterator it;
void add(ll y,ll x){
while(y < 750005){
b[y] += x;
y += y&-y;
}
}
ll sum(ll y){
ll x = 0;
while(y > 0){
x += b[y];
y -= y&-y;
}
return x;
}
ll calc(ll t, bool flag){
vector<ll>v,g;
M1.clear();
M2.clear();
for(int i=1; i<=3 * n; i++){
beg[i].clear();
er[i].clear();
}
for(int i=1; i<=n; i++){
v.pb(x[i] + y[i]);
v.pb(x[i] + y[i] + t + 1);
g.pb(x[i] - y[i] - t);
g.pb(x[i] - y[i]);
g.pb(x[i] - y[i] + t);
}
sort(v.begin() , v.end());
sort(g.begin() , g.end());
int p = 0;
for(int i=0; i<v.size(); i++){
if(!i || v[i] != v[i - 1])p++;
M1[v[i]] = p;
}
p = 0;
for(int i=0; i<g.size(); i++){
if(!i || g[i] != g[i - 1])p++;
M2[g[i]] = p;
}
vector<pair<ll,ll> >f;
for(int i=1; i<=n; i++){
er[M1[x[i] + y[i] + t + 1]].pb(i);
beg[M1[x[i] + y[i]]].pb(i);
f.pb({x[i] + y[i] , i});
}
sort(f.begin() , f.end());
ll ret = 0;
for(int i=1; i<=2 * n; i++){
for(auto ind : er[i]){
add(M2[x[ind] - y[ind]] , -1);
//if(flag)st.erase(st.find({M2[x[ind] - y[ind]] , ind}));
}
for(auto ind : beg[i]){
ret += sum(M2[x[ind] - y[ind] + t]) - sum(M2[x[ind] - y[ind] - t] - 1);
//if(flag)it = st.lower_bound({M2[x[ind] - y[ind] - t] , 0});
//if(flag)
// while(it != st.end() && (*it).f <= M2[x[ind] - y[ind] + t]){
// A.pb(abs(x[ind] - x[(*it).s]) + abs(y[ind] - y[(*it).s]));
// it++;
// }
add(M2[x[ind] - y[ind]] , 1);
//if(flag)st.insert({M2[x[ind] - y[ind]] , ind});
}
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> k;
for(int i=1; i<=n; i++){
cin >> x[i] >> y[i];
}
ll l=0,r = 4000000000,mid,ans = 0;
while(r >= l){
mid = (l + r) / 2;
if(calc(mid , 0) >= k){
ans = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
calc(ans - 1 , 1);
sort(A.begin() , A.end());
for(auto F : A)
cout << F << '\n';
for(int i=0; i<k - (int)A.size(); i++)
cout << ans << '\n';
return 0;
}
Compilation message
road_construction.cpp: In function 'long long int calc(long long int, bool)':
road_construction.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0; i<v.size(); i++){
| ~^~~~~~~~~
road_construction.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0; i<g.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
38720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10018 ms |
152552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10107 ms |
152332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10107 ms |
152332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
38720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
38720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
