#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LIM = 1000000000000000;
int n, k;
int l[40000000], r[40000000];
int s[40000000], e[40000000];
int val[40000000];
int nodeCnt = 0;
ll locList[250002];
int root[250002];
int rootCnt;
vector<ll> yVal;
int newNode(int _s, int _e, int _v=0, int _l=0, int _r=0){
nodeCnt++;
s[nodeCnt] = _s, e[nodeCnt] = _e, val[nodeCnt] = _v;
l[nodeCnt] = _l, r[nodeCnt] = _r;
return nodeCnt;
}
void addPoint(int i, int x){
if(s[i] == e[i]){
val[i]++;
return;
}
int m = (s[i] + e[i] + LIM + LIM) / 2 - LIM;
if(x <= m){
l[i] = newNode(s[i], m, val[l[i]], l[l[i]], r[l[i]]);
addPoint(l[i], x);
}
else{
r[i] = newNode(m+1, e[i], val[r[i]], l[r[i]], r[r[i]]);
addPoint(r[i], x);
}
val[i] = val[l[i]] + val[r[i]];
}
int sumCnt = 0;
int sum(int i, int rs, int re){
sumCnt++;
if(rs <= s[i] && e[i] <= re) return val[i];
int m = (s[i] + e[i] + LIM + LIM) / 2 - LIM;
int ret = 0;
if(rs <= m && l[i]) ret += sum(l[i], rs, re);
if(m < re && r[i]) ret += sum(r[i], rs, re);
return ret;
}
void newPoint(int x, int y){
if(locList[rootCnt] != x){
root[rootCnt+1] = newNode(0, n, val[root[rootCnt]], l[root[rootCnt]], r[root[rootCnt]]);
locList[++rootCnt] = x;
}
addPoint(root[rootCnt], y);
}
int sum(ll xs, ll xe, ll ys, ll ye){
xe = upper_bound(locList, locList+rootCnt+1, xe) - locList - 1;
xs = lower_bound(locList, locList+rootCnt+1, xs) - locList - 1;
ye = upper_bound(yVal.begin(), yVal.end(), ye) - yVal.begin() - 1;
ys = lower_bound(yVal.begin(), yVal.end(), ys) - yVal.begin();
return sum(root[xe], ys, ye) - sum(root[xs], ys, ye);
}
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);
// n = 1000, k = 250000;
for(int i=1; i<=n; i++){
scanf("%lld %lld", &arr[i].first, &arr[i].second);
// arr[i].first = rand();
// arr[i].second = rand();
ll tx = arr[i].first, ty = arr[i].second;
arr[i].first = tx + ty, arr[i].second = tx - ty;
yVal.push_back(arr[i].second);
}
sort(arr+1, arr+n+1);
sort(yVal.begin(), yVal.end());
yVal.erase(unique(yVal.begin(), yVal.end()), yVal.end());
locList[0] = -1e15;
root[0] = newNode(0, n);
for(int i=1; i<=n; i++){
newPoint(arr[i].first, arr[i].second);
}
for(int i=1; i<=n; i++){
ll MIN = 0, MAX = 1e10, ANS = 1e10;
cnt[i]++;
while(MIN <= MAX){
ll MID = (MIN + MAX) / 2;
if(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;
int turnCnt = 0;
while(k--){
assert(!pq.empty());
pair<ll, int> p = pq.top(); pq.pop();
if(k%2) printf("%lld\n", p.first);
// if(++turnCnt % 1000 == 0) printf("%d\n", turnCnt);
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;
sumCnt = 0;
if(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;
// printf("%d\n", sumCnt);
}
minDist[i] = ANS;
pq.push(make_pair(ANS, i));
}
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:114:9: warning: unused variable 'turnCnt' [-Wunused-variable]
114 | int turnCnt = 0;
| ^~~~~~~
road_construction.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%lld %lld", &arr[i].first, &arr[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2143 ms |
3312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8058 ms |
108616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6812 ms |
106552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6812 ms |
106552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2143 ms |
3312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2143 ms |
3312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
