#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Query {
int mode; /// 0: �� �߰�, 1: ���� ����, 2: ���� ��
ll x, y1, y2; int idx;
Query(){}
Query(int mode, ll x, ll y1, ll y2, int idx): mode(mode), x(x), y1(y1), y2(y2), idx(idx){}
bool operator<(const Query &r)const{
if(x != r.x) return x<r.x;
return mode < r.mode;
}
};
struct Fenwick {
int n;
int tree[500002];
void init(){
memset(tree, 0, sizeof(tree));
}
void add(int x, int y){
x++;
while(x <= n){
tree[x] += y;
x += x&-x;
}
}
int sum(int x){
x++;
int ret = 0;
while(x){
ret += tree[x];
x -= x&-x;
}
return ret;
}
int sum(int l, int r){
return sum(r) - sum(l-1);
}
} tree;
struct segTree{
vector<pair<int, ll> > tree[1000002];
void add(int i, int l, int r, int x, int arg1, ll arg2){
tree[i].push_back(make_pair(arg1, arg2));
if(l==r) return;
int m = (l+r)>>1;
if(x<=m) add(i*2, l, m, x, arg1, arg2);
else add(i*2+1, m+1, r, x, arg1, arg2);
}
void addAns(int i, int l, int r, int s, int e, ll lim, vector<int> &tVec){
if(r<s || e<l) return;
if(s<=l && r<=e){
auto it = tree[i].rbegin();
while(it != tree[i].rend() && it->second >= lim){
tVec.push_back(it->first);
++it;
}
return;
}
int m = (l+r)>>1;
addAns(i*2, l, m, s, e, lim, tVec);
addAns(i*2+1, m+1, r, s, e, lim, tVec);
}
} tree2;
int n, k;
vector<ll> yVal;
pair<ll, ll> arr[250002];
int cnt[250002];
int tyloc[250002];
ll minDist[250002];
ll totalMin;
vector<ll> ans;
int main(){
scanf("%d %d", &n, &k);
// n = 250000, k = 250000;
tree.n = n;
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());
for(int i=1; i<=n; i++){
tyloc[i] = lower_bound(yVal.begin(), yVal.end(), arr[i].second) - yVal.begin();
}
{
ll MIN = 0, MAX = 1e10, ANS = 1e10;
while(MIN <= MAX){
ll MID = (MIN + MAX) / 2;
ll sum = -n;
tree.init();
vector<Query> vec;
for(int i=1; i<=n; i++){
int y2 = upper_bound(yVal.begin(), yVal.end(), arr[i].second + MID) - yVal.begin() - 1;
int y1 = lower_bound(yVal.begin(), yVal.end(), arr[i].second - MID) - yVal.begin();
vec.push_back(Query(0, arr[i].first, tyloc[i], tyloc[i], i));
vec.push_back(Query(1, arr[i].first - MID - 1, y1, y2, i));
vec.push_back(Query(2, arr[i].first + MID, y1, y2, i));
}
sort(vec.begin(), vec.end());
for(Query query: vec){
if(query.mode == 0) tree.add(query.y1, 1);
else if(query.mode == 1) sum -= tree.sum(query.y1, query.y2);
else sum += tree.sum(query.y1, query.y2);
}
if(sum >= k*2){
ANS = MID;
MAX = MID-1;
}
else MIN = MID+1;
}
totalMin = ANS;
}
totalMin--;
vector<Query> vec;
for(int i=1; i<=n; i++){
int y2 = upper_bound(yVal.begin(), yVal.end(), arr[i].second + totalMin) - yVal.begin() - 1;
int y1 = lower_bound(yVal.begin(), yVal.end(), arr[i].second - totalMin) - yVal.begin();
vec.push_back(Query(0, arr[i].first, tyloc[i], tyloc[i], i));
vec.push_back(Query(2, arr[i].first + totalMin, y1, y2, i));
}
sort(vec.begin(), vec.end());
for(Query query: vec){
if(query.mode == 0){
tree2.add(1, 0, n, query.y1, query.idx, query.x);
}
else{
vector<int> tVec;
tree2.addAns(1, 0, n, query.y1, query.y2, arr[query.idx].second - totalMin, tVec);
for(auto x: tVec){
if(x <= query.idx) continue;
ans.push_back(max(abs(arr[query.idx].first - arr[x].first), abs(arr[query.idx].second - arr[x].second)));
}
}
}
sort(ans.begin(), ans.end());
while(ans.size() < k) ans.push_back((totalMin + 1));
for(int i=0; i<k; i++) printf("%lld\n", ans[i]);
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:165:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
165 | while(ans.size() < k) ans.push_back((totalMin + 1));
| ~~~~~~~~~~~^~~
road_construction.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%lld %lld", &arr[i].first, &arr[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
30632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5193 ms |
140632 KB |
Output is correct |
| 2 |
Correct |
5405 ms |
140632 KB |
Output is correct |
| 3 |
Correct |
107 ms |
30544 KB |
Output is correct |
| 4 |
Correct |
5007 ms |
140348 KB |
Output is correct |
| 5 |
Correct |
5379 ms |
140752 KB |
Output is correct |
| 6 |
Correct |
5302 ms |
140756 KB |
Output is correct |
| 7 |
Correct |
5221 ms |
139988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7942 ms |
138144 KB |
Output is correct |
| 2 |
Correct |
7662 ms |
137868 KB |
Output is correct |
| 3 |
Correct |
25 ms |
25644 KB |
Output is correct |
| 4 |
Correct |
5188 ms |
137812 KB |
Output is correct |
| 5 |
Correct |
4689 ms |
138068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7942 ms |
138144 KB |
Output is correct |
| 2 |
Correct |
7662 ms |
137868 KB |
Output is correct |
| 3 |
Correct |
25 ms |
25644 KB |
Output is correct |
| 4 |
Correct |
5188 ms |
137812 KB |
Output is correct |
| 5 |
Correct |
4689 ms |
138068 KB |
Output is correct |
| 6 |
Incorrect |
7680 ms |
137640 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
30632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
30632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
