#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3z2QF2y ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
#define all(a) a.begin(), a.end()
const int _n=250011;
using namespace __gnu_pbds;
typedef tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
struct fenwick{
ordered_set bit[_n];
void add(int i,int x,int id){
// 0 based
i+=1;
while(i<_n){
bit[i].insert({x,id});
i+=i&-i;
}
}
int query(int i,int l,int r){
i+=1;
int res=0;
while(i){
res+=bit[i].order_of_key({r+1,0})-bit[i].order_of_key({l,0});
i-=i&-i;
}
return res;
}
};
signed main(){
_3z2QF2y;
int n,k;
cin>>n>>k;
k*=2;
vec(pii) a(n);
rep(i,n) cin>>a[i].fi>>a[i].se;
vi xs,ys;
rep(i,n){
int u=a[i].fi-a[i].se,v=a[i].fi+a[i].se;
xs.pb(u);
ys.pb(v);
}
sort(all(xs));
xs.erase(unique(all(xs)),xs.end());
sort(all(ys));
ys.erase(unique(all(ys)),ys.end());
fenwick bit;
rep(i,n){
int u=a[i].fi-a[i].se,v=a[i].fi+a[i].se;
// print(u,v);
bit.add(lower_bound(all(xs),u)-xs.begin(),v,i);
}
// print(bit.query(2,-2,2));
auto eval=[&](int x,int y,int d)->int{
pii u={x-y-d,x+y+d};
pii v={x-y+d,x+y-d};
int sx=u.fi,tx=v.fi;
int sy=v.se,ty=u.se;
auto it=lower_bound(all(xs),sx);
auto ti=upper_bound(all(xs),tx);
int res=0;
if(ti!=xs.begin()){
// print(tx,sy,ty);
tx=prev(ti)-xs.begin();
res+=bit.query(tx,sy,ty);
if(it!=xs.begin()){
sx=prev(it)-xs.begin();
res-=bit.query(sx,sy,ty);
}
}
// int nres=0;
// rep(i,n){
// if(abs(a[i].fi-x)+abs(a[i].se-y)<=d) nres+=1;
// }
// if(res!=nres){
// print(x,y,d,res,nres);
// exit(0);
// }
return res;
};
using T=pair<int,pii>;
priority_queue<T,vec(T),greater<T>> pq;
vi rbe(n,1);
auto push=[&](int i){
int l=1,r=3e9+1;
int c=-1,val=-1;
while(l<=r){
int m=(l+r)/2;
int nval=eval(a[i].fi,a[i].se,m);
if(nval>rbe[i]){
val=nval-rbe[i],c=m,r=m-1;
}else{
l=m+1;
}
}
if(c!=-1){
pq.push({c,{val,i}});
rbe[i]+=val;
}
};
rep(i,n){
push(i);
}
vi pns;
while(sz(pq) and k>0){
auto top=pq.top();
pq.pop();
while(top.se.fi--){
pns.pb(top.fi);
k-=1;
}
push(top.se.se);
}
assert(sz(pns)%2==0);
for(int i=0;i<sz(pns);i+=2){
cout<<pns[i]<<"\n";
}
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8610 ms |
31268 KB |
Output is correct |
| 2 |
Correct |
8523 ms |
31236 KB |
Output is correct |
| 3 |
Incorrect |
5237 ms |
31056 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10101 ms |
178940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10091 ms |
178392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10091 ms |
178392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8610 ms |
31268 KB |
Output is correct |
| 2 |
Correct |
8523 ms |
31236 KB |
Output is correct |
| 3 |
Incorrect |
5237 ms |
31056 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8610 ms |
31268 KB |
Output is correct |
| 2 |
Correct |
8523 ms |
31236 KB |
Output is correct |
| 3 |
Incorrect |
5237 ms |
31056 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
