#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(size_t a = 0; a < (b); a++)
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=3e5+10;
const int SS=1<<30;
struct item{
ll val;
int id;
item *l,*r;
};
vi wyn;
vector<pair<int,int> >w;
bool bb[N];
vi ans,pom[N];
void Insert(pitem v,int ind,int x,int xd,int l=SS*(-1),int r=SS-1){
v->val+=x;
if(l==r) {v->id=xd;return;}
int sr=l+(r-l)/2;
if(ind>sr){
if(!(v->r)){
pitem xd=new item;
xd->l=nullptr,xd->r=nullptr,xd->val=0;
v->r=xd;
}
Insert(v->r,ind,x,xd,sr+1,r);
}else{
if(!(v->l)){
pitem xd=new item;
xd->l=nullptr,xd->r=nullptr,xd->val=0;
v->l=xd;
}
Insert(v->l,ind,x,xd,l,sr);
}
}
void clear(pitem v){
if(!v) return;
clear(v->l),clear(v->r);
delete v;
}
ll Query(pitem v,int pocz,int kon,int p=SS*(-1),int k=SS-1){
if(p>kon or k<pocz or !v) return 0;
if(p>=pocz and k<=kon) return v->val;
else{
int sr=p+(k-p)/2;
return Query(v->l,pocz,kon,p,sr)+Query(v->r,pocz,kon,sr+1,k);
}
}
void divide(int l,int r,pitem v,int k){
if(!v or wyn.size()==k) return;
if(v->val==0) return;
if(l==r){
wyn.push_back(v->id);
return;
}
int sr=l+(r-l)/2;
divide(l,sr,v->l,k),divide(sr+1,r,v->r,k);
}
void Query2(pitem v,int pocz,int kon,int kk,int p=SS*(-1),int k=SS-1){
if(p>kon or k<pocz or !v) return;
if(p>=pocz and k<=kon) divide(p,k,v,kk);
else{
int sr=p+(k-p)/2;
Query2(v->l,pocz,kon,kk,p,sr),Query2(v->r,pocz,kon,kk,sr+1,k);
}
}
bool check(int x,ll l){;
int xd=(x+1)*2-1;
int wsk=0;
pitem k=new item;
k->val=0,k->l=nullptr,k->r=nullptr;
ll res=0;
rep(i,w.size()){
if(i and w[i].fi==w[i-1].fi) continue;
int curr=i;
while(w[wsk].fi<w[i].fi-x) Insert(k,w[wsk].se,-1,0),wsk++;
while(curr<w.size() and w[curr].fi==w[i].fi) res+=Query(k,w[curr].se-x,w[curr].se+x),Insert(k,w[curr].se,1,curr),curr++;
}
clear(k);
return res>=l;
}
int bs(ll l){
int pocz=1,kon=(ll)(1e9)*2;
int sr,res=0;
while(pocz<=kon){
sr=(pocz+kon)/2;
if(check(sr,l)) res=sr,kon=sr-1;
else pocz=sr+1;
}
return res;
}
void solve(){
int n,il;
cin>>n>>il;
rep(i,n){
int x,y;
cin>>x>>y;
int x1=x-y,y1=x+y;
w.push_back({x1,y1});
}
sort(w.begin(),w.end());
int xd=bs(il);
int x,wsk;
if(xd>1){
x=xd-1;
pitem k=new item;
k->val=0,k->l=nullptr,k->r=nullptr;
wsk=0;
rep(i,w.size()){
if(i and w[i].fi==w[i-1].fi) continue;
int curr=i;
while(w[wsk].fi<w[i].fi-x) Insert(k,w[wsk].se,-1,0),wsk++;
while(curr<w.size() and w[curr].fi==w[i].fi){
Query2(k,w[curr].se-x,w[curr].se+x,il),Insert(k,w[curr].se,1,curr);
pom[curr]=wyn;
rep(j,wyn.size()) ans.push_back(max(abs(w[curr].fi-w[wyn[j]].fi),abs(w[curr].se-w[wyn[j]].se)));
curr++;
wyn.clear();
}
}
clear(k);
}
pitem k=new item;
k->val=0,k->l=nullptr,k->r=nullptr;
x=xd,wsk=0;
rep(i,w.size()){
if(i and w[i].fi==w[i-1].fi) continue;
int curr=i;
while(w[wsk].fi<w[i].fi-x) Insert(k,w[wsk].se,-1,0),wsk++;
while(curr<w.size() and w[curr].fi==w[i].fi){
Query2(k,w[curr].se-x,w[curr].se+x,il),Insert(k,w[curr].se,1,curr);
rep(j,pom[curr].size()) bb[pom[curr][j]]=1;
rep(j,wyn.size()) if(!bb[wyn[j]] and ans.size()<il) ans.push_back(max(abs(w[curr].fi-w[wyn[j]].fi),abs(w[curr].se-w[wyn[j]].se)));
rep(j,pom[curr].size()) bb[pom[curr][j]]=0;
curr++;
wyn.clear();
if(ans.size()==il) break;
}
if(ans.size()==il) break;
}
sort(ans.begin(),ans.end());
rep(i,ans.size()) cout<<ans[i]<<"\n";
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
solve();
}
Compilation message
road_construction.cpp: In function 'void divide(int, int, item*, int)':
road_construction.cpp:55:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
55 | if(!v or wyn.size()==k) return;
| ~~~~~~~~~~^~~
road_construction.cpp: In function 'bool check(int, ll)':
road_construction.cpp:82:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while(curr<w.size() and w[curr].fi==w[i].fi) res+=Query(k,w[curr].se-x,w[curr].se+x),Insert(k,w[curr].se,1,curr),curr++;
| ~~~~^~~~~~~~~
road_construction.cpp:73:6: warning: unused variable 'xd' [-Wunused-variable]
73 | int xd=(x+1)*2-1;
| ^~
road_construction.cpp: In function 'void solve()':
road_construction.cpp:4:39: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
4 | #define rep(a, b) for(size_t a = 0; a < (b); a++)
| ^
road_construction.cpp:100:2: note: in expansion of macro 'rep'
100 | rep(i,n){
| ^~~
road_construction.cpp:118:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | while(curr<w.size() and w[curr].fi==w[i].fi){
| ~~~~^~~~~~~~~
road_construction.cpp:135:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | while(curr<w.size() and w[curr].fi==w[i].fi){
| ~~~~^~~~~~~~~
road_construction.cpp:138:51: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
138 | rep(j,wyn.size()) if(!bb[wyn[j]] and ans.size()<il) ans.push_back(max(abs(w[curr].fi-w[wyn[j]].fi),abs(w[curr].se-w[wyn[j]].se)));
| ~~~~~~~~~~^~~
road_construction.cpp:142:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
142 | if(ans.size()==il) break;
| ~~~~~~~~~~^~~~
road_construction.cpp:144:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
144 | if(ans.size()==il) break;
| ~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
16588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10029 ms |
174848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
413 ms |
289592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
413 ms |
289592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
16588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
16588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
