#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;
struct item{
int val,sum,il;
ll prior;
item *l,*r;
};
vector<pair<int,int> >w;
bool bb[N];
vector<ll> ans;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
unordered_map<int,int>m;
deque<int> deq[N];
pair<pitem,pitem> split(pitem v,int x){
if(!v) return {nullptr,nullptr};
if((v->val)<=x){
pair<pitem,pitem> p=split(v->r,x);
v->r=p.fi;
v->sum=((v->l)!=nullptr?v->l->sum:0)+((v->r)!=nullptr?v->r->sum:0)+(v->il);
return {v,p.se};
}else{
pair<pitem,pitem> p=split(v->l,x);
v->l=p.se;
v->sum=((v->l)!=nullptr?v->l->sum:0)+((v->r)!=nullptr?v->r->sum:0)+(v->il);
return {p.fi,v};
}
}
pitem merge(pitem v1,pitem v2){
if(!v1 or !v2) return (!v1?v2:v1);
if((v1->prior)>(v2->prior)){
v1->r=merge(v1->r,v2);
v1->sum=((v1->l)!=nullptr?v1->l->sum:0)+((v1->r)!=nullptr?v1->r->sum:0)+(v1->il);
return v1;
}else{
v2->l=merge(v1,v2->l);
v2->sum=((v2->l)!=nullptr?v2->l->sum:0)+((v2->r)!=nullptr?v2->r->sum:0)+(v2->il);
return v2;
}
}
pitem add(pitem v,int a){
pair<pitem,pitem> curr=split(v,a);
pair<pitem,pitem> curr2=split(curr.fi,a-1);
if(!curr2.se){
pitem nn=new item;
nn->val=a,nn->il=1,nn->sum=1,nn->l=nullptr,nn->r=nullptr;
nn->prior=uniform_int_distribution<ll>(1,1000LL*1000LL*1000LL*1000LL)(rng);
v=merge(merge(curr2.fi,nn),curr.se);
}else{
curr2.se->il++,curr2.se->sum++;
v=merge(merge(curr2.fi,curr2.se),curr.se);
}
return v;
}
pitem del(pitem v,int a){
pair<pitem,pitem> curr=split(v,a);
pair<pitem,pitem> curr2=split(curr.fi,a-1);
if(curr2.se->il==1) v=merge(curr2.fi,curr.se);
else{
curr2.se->il--,curr2.se->sum--;
v=merge(merge(curr2.fi,curr2.se),curr.se);
}
return v;
}
void clear(pitem v){
if(!v) return;
clear(v->l),clear(v->r);
delete v;
}
bool check(ll x,ll l){;
int wsk=0;
pitem k=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) k=del(k,w[wsk].se),wsk++;
while(curr<(int)w.size() and w[curr].fi==w[i].fi){
pair<int,int>prz={max((ll)1e9*2LL*(-1),w[curr].se-x),min((ll)1e9*2LL,w[curr].se+x)};
pair<pitem,pitem> c=split(k,prz.se);
pair<pitem,pitem> curr2=split(c.fi,prz.fi-1);
res+=(!curr2.se?0:curr2.se->sum);
k=merge(merge(curr2.fi,curr2.se),c.se);
k=add(k,w[curr].se);
curr++;
}
}
clear(k);
return res>=l;
}
ll bs(ll l){
ll pocz=1,kon=(ll)(1e9)*4;
ll 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 odczyt(pitem k,int j){
if(!k) return;
deque<int> d=deq[m[k->val]];
while(d.size()){
pair<int,int> nn={d.front(),k->val};
ans.push_back(max(abs(w[j].fi-nn.fi),abs(w[j].se-nn.se)));
d.pop_front();
}
odczyt(k->l,j),odczyt(k->r,j);
}
void solve(){
pitem k=nullptr;
k=add(k,2);
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(),[](pair<int,int> a,pair<int,int> b){
return a.se<b.se;
});
int akt=0;
rep(i,w.size()) if(!i or w[i].se!=w[i-1].se) m[w[i].se]=akt++;
sort(w.begin(),w.end());
ll xd=bs(il);
if(xd!=1){
ll x=xd-1,wsk=0;
pitem k=nullptr;
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) deq[m[w[wsk].se]].pop_front(),k=del(k,w[wsk].se),wsk++;
while(curr<(int)w.size() and w[curr].fi==w[i].fi){
pair<int,int>prz={max((ll)1e9*2LL*(-1),w[curr].se-x),min((ll)1e9*2LL,w[curr].se+x)};
pair<pitem,pitem> c=split(k,prz.se);
pair<pitem,pitem> curr2=split(c.fi,prz.fi-1);
odczyt(curr2.se,curr);
k=merge(merge(curr2.fi,curr2.se),c.se);
k=add(k,w[curr].se);
deq[m[w[curr].se]].push_back(w[curr].fi);
curr++;
}
}
}
sort(ans.begin(),ans.end());
rep(i,ans.size()) cout<<ans[i]<<"\n";
for(int i=ans.size();i<il;i++) cout<<xd<<"\n";
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
solve();
}
Compilation message
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:123:2: note: in expansion of macro 'rep'
123 | rep(i,n){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
208152 KB |
Output is correct |
| 2 |
Correct |
216 ms |
208196 KB |
Output is correct |
| 3 |
Incorrect |
198 ms |
207132 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2311 ms |
573280 KB |
Output is correct |
| 2 |
Correct |
2258 ms |
573276 KB |
Output is correct |
| 3 |
Correct |
193 ms |
206932 KB |
Output is correct |
| 4 |
Correct |
2163 ms |
584804 KB |
Output is correct |
| 5 |
Correct |
2268 ms |
570436 KB |
Output is correct |
| 6 |
Correct |
2256 ms |
571228 KB |
Output is correct |
| 7 |
Correct |
2312 ms |
572624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5586 ms |
599672 KB |
Output is correct |
| 2 |
Correct |
5648 ms |
599712 KB |
Output is correct |
| 3 |
Correct |
128 ms |
202260 KB |
Output is correct |
| 4 |
Correct |
2075 ms |
569276 KB |
Output is correct |
| 5 |
Correct |
5294 ms |
491872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5586 ms |
599672 KB |
Output is correct |
| 2 |
Correct |
5648 ms |
599712 KB |
Output is correct |
| 3 |
Correct |
128 ms |
202260 KB |
Output is correct |
| 4 |
Correct |
2075 ms |
569276 KB |
Output is correct |
| 5 |
Correct |
5294 ms |
491872 KB |
Output is correct |
| 6 |
Correct |
5805 ms |
587744 KB |
Output is correct |
| 7 |
Correct |
5869 ms |
599456 KB |
Output is correct |
| 8 |
Correct |
127 ms |
202180 KB |
Output is correct |
| 9 |
Incorrect |
134 ms |
202220 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
208152 KB |
Output is correct |
| 2 |
Correct |
216 ms |
208196 KB |
Output is correct |
| 3 |
Incorrect |
198 ms |
207132 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
208152 KB |
Output is correct |
| 2 |
Correct |
216 ms |
208196 KB |
Output is correct |
| 3 |
Incorrect |
198 ms |
207132 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
