#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int SZ=1<<17;
vector<int> P[250000];
vector<pair<int,int>> U[250000];
vector<long long> ans, x, y;
int tree[2*SZ], X[250000], Y[250000];
void update(int n, int v)
{
for(;n<=250000;n+=n&-n) tree[n]+=v;
}
int get_cnt(int n)
{
int ret=0;
for(;n;n-=n&-n) ret+=tree[n];
return ret;
}
long long solve(long long K)
{
int j=0;
long long ret=0;
memset(tree,0,sizeof(tree));
for(int i=0;i<x.size();i++) {
for(;x[j]+K<x[i];j++) for(auto[u,k]: U[j]) update(u+1,-1);
for(auto[u,k]: U[i]) update(u+1,1);
for(auto[u,k]: U[i]) ret+=get_cnt(upper_bound(y.begin(),y.end(),y[u]+K)-y.begin())-get_cnt(lower_bound(y.begin(),y.end(),y[u]-K)-y.begin())-1;
}
return ret;
}
void add_tree(int n, int i)
{
P[n].push_back(i);
for(tree[n+=SZ]++;n>>=1;) tree[n]=tree[2*n]+tree[2*n+1];
}
void get_ans(int n1, int n2, int i, long long K, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(n2<n1 || n2<s || e<n1 || tree[bit]==0) return;
if(s==e) {
for(int j=0;j<P[m].size();j++) {
while(j<P[m].size() && 1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i])>K) {
swap(P[m][j],P[m].back());
P[m].pop_back();
tree[bit]--;
}
if(j<P[m].size() && i!=P[m][j]) ans.push_back(1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i]));
}
return;
}
get_ans(n1,n2,i,K,2*bit,s,m);
get_ans(n1,n2,i,K,2*bit+1,m+1,e);
tree[bit]=tree[2*bit]+tree[2*bit+1];
}
long long solve2(long long K)
{
long long ret=0;
memset(tree,0,sizeof(tree));
for(int i=0;i<x.size();i++) {
for(auto[u,k]: U[i]) add_tree(u,k);
for(auto[u,k]: U[i]) get_ans(lower_bound(y.begin(),y.end(),y[u]-K)-y.begin(),upper_bound(y.begin(),y.end(),y[u]+K)-y.begin()-1,k,K);
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, K;
long long s=0, e=4000000000LL;
cin>>N>>K;
for(int i=0;i<N;i++) {
cin>>X[i]>>Y[i];
x.push_back(X[i]+Y[i]);
y.push_back(X[i]-Y[i]);
}
sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin());
sort(y.begin(),y.end()); y.resize(unique(y.begin(),y.end())-y.begin());
for(int i=0;i<N;i++) U[lower_bound(x.begin(),x.end(),X[i]+Y[i])-x.begin()].emplace_back(lower_bound(y.begin(),y.end(),X[i]-Y[i])-y.begin(),i);
while(s<=e) {
long long m=(s+e)>>1;
if(solve(m)<K) s=m+1;
else e=m-1;
}
solve2(e);
sort(ans.begin(),ans.end());
while(ans.size()<K) ans.push_back(s);
for(auto a: ans) cout<<a<<'\n';
return 0;
}
Compilation message
road_construction.cpp: In function 'long long int solve(long long int)':
road_construction.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0;i<x.size();i++) {
| ~^~~~~~~~~
road_construction.cpp: In function 'void get_ans(int, int, int, long long int, int, int, int)':
road_construction.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int j=0;j<P[m].size();j++) {
| ~^~~~~~~~~~~~
road_construction.cpp:56:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | while(j<P[m].size() && 1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i])>K) {
| ~^~~~~~~~~~~~
road_construction.cpp:61:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if(j<P[m].size() && i!=P[m][j]) ans.push_back(1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i]));
| ~^~~~~~~~~~~~
road_construction.cpp: In function 'long long int solve2(long long int)':
road_construction.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i=0;i<x.size();i++) {
| ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:106:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
106 | while(ans.size()<K) ans.push_back(s);
| ~~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
17732 KB |
Output is correct |
| 2 |
Correct |
79 ms |
17808 KB |
Output is correct |
| 3 |
Correct |
78 ms |
17784 KB |
Output is correct |
| 4 |
Correct |
72 ms |
17840 KB |
Output is correct |
| 5 |
Incorrect |
74 ms |
16612 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3034 ms |
66508 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5700 ms |
54052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5700 ms |
54052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
17732 KB |
Output is correct |
| 2 |
Correct |
79 ms |
17808 KB |
Output is correct |
| 3 |
Correct |
78 ms |
17784 KB |
Output is correct |
| 4 |
Correct |
72 ms |
17840 KB |
Output is correct |
| 5 |
Incorrect |
74 ms |
16612 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
17732 KB |
Output is correct |
| 2 |
Correct |
79 ms |
17808 KB |
Output is correct |
| 3 |
Correct |
78 ms |
17784 KB |
Output is correct |
| 4 |
Correct |
72 ms |
17840 KB |
Output is correct |
| 5 |
Incorrect |
74 ms |
16612 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
