#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct PST{
struct Node{
int created;
Node *l, *r;
int s, e;
int val;
Node(){
l = r = nullptr;
}
Node(int s, int e, int created): s(s), e(e), created(created){
l = r = nullptr;
val = 0;
}
Node* decent(int c){
Node* ret = new Node(s, e, c);
ret->val = val;
ret->l = l, ret->r = r;
return ret;
}
~Node(){
if(l && created == l->created) delete l;
if(r && created == r->created) delete r;
}
void addPoint(int x){
if(s==e){
val++;
return;
}
int m = (s+e)>>1;
if(x <= m){
if(l && l->created == created){}
else if(l) l = l->decent(created);
else l = new Node(s, m, created);
l->addPoint(x);
}
else{
if(r && r->created == created){}
else if(r) r = r->decent(created);
else r = new Node(m+1, e, created);
r->addPoint(x);
}
val = (l ? l->val : 0) + (r ? r->val : 0);
}
int sum(int rs, int re){
if(rs <= s && e <= re) return val;
int m = (rs+re)>>1;
int ret = 0;
if(rs <= m && l) ret += l->sum(rs, re);
if(m < re && r) ret += r->sum(rs, re);
return ret;
}
};
int sz;
Node* root[250002];
vector<ll> locList;
PST(){
sz = 0;
locList.push_back(-2e9-2);
root[0] = new Node(-2e9, 2e9, 0);
}
void deleteNodes(){
for(int i=sz; i>=0; i--) delete root[i];
}
void addPoint(ll x, ll y){
if(locList.back() != x){
root[sz+1] = root[sz]->decent(sz);
sz++;
locList.push_back(x);
}
root[sz]->addPoint(y);
}
ll sum(ll xs, ll xe, ll ys, ll ye){
xe = upper_bound(locList.begin(), locList.end(), xe) - locList.begin() - 1;
xs = lower_bound(locList.begin(), locList.end(), xs) - locList.begin() - 1;
return root[xe]->sum(ys, ye) - root[xs]->sum(ys, ye);
}
} tree;
int n, k;
pair<ll, ll> arr[250002];
int cnt[250002];
ll minDist[250002];
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
int main(){
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++){
scanf("%lld %lld", &arr[i].first, &arr[i].second);
ll tx = arr[i].first, ty = arr[i].second;
arr[i].first = tx + ty, arr[i].second = tx - ty;
}
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++){
tree.addPoint(arr[i].first, arr[i].second);
}
for(int i=1; i<=n; i++){
ll MIN = 0, MAX = 2e9, ANS = 2e9;
cnt[i]++;
while(MIN <= MAX){
ll MID = (MIN + MAX) / 2;
if(tree.sum(arr[i].first - MID, arr[i].first + MID, arr[i].second - MID, arr[i].second + MID) > cnt[i]){
ANS = MID;
MAX = MID-1;
}
else MIN = MID+1;
}
minDist[i] = ANS;
pq.push(make_pair(ANS, i));
}
k *= 2;
while(k--){
assert(!pq.empty());
pair<ll, int> p = pq.top(); pq.pop();
if(k%2) printf("%lld\n", p.first);
int i = p.second;
cnt[i]++;
if(cnt[i] == n) continue;
ll MIN = 0, MAX = 2e9, ANS = 2e9;
while(MIN <= MAX){
ll MID = (MIN + MAX) / 2;
if(tree.sum(arr[i].first - MID, arr[i].first + MID, arr[i].second - MID, arr[i].second + MID) > cnt[i]){
ANS = MID;
MAX = MID-1;
}
else MIN = MID+1;
}
minDist[i] = ANS;
pq.push(make_pair(ANS, i));
}
tree.deleteNodes();
}
Compilation message
road_construction.cpp: In constructor 'PST::Node::Node(int, int, int)':
road_construction.cpp:11:16: warning: 'PST::Node::e' will be initialized after [-Wreorder]
11 | int s, e;
| ^
road_construction.cpp:9:13: warning: 'int PST::Node::created' [-Wreorder]
9 | int created;
| ^~~~~~~
road_construction.cpp:17:9: warning: when initialized here [-Wreorder]
17 | Node(int s, int e, int created): s(s), e(e), created(created){
| ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%lld %lld", &arr[i].first, &arr[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1479 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10035 ms |
394872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1614 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1614 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1479 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1479 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
