#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <cstdlib>
#include <set>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
using namespace std;
const long long INF = (int)2e9 + 7;
struct Node
{
int x;
int l, r;
}seg[30202020];
int cnt = 0;
int init(int s, int e)
{
int ind = cnt++;
seg[ind].x = 0;
if(s + 1 == e) return ind;
int mid = s + e >> 1;
seg[ind].l = init(s, mid);
seg[ind].r = init(mid, e);
return ind;
}
int upd(int nd, int s, int e, int pos)
{
int ind = cnt++;
seg[ind] = seg[nd];
if(s + 1 == e)
{
++seg[ind].x;
return ind;
}
int mid = s + e >> 1;
if(pos < mid) seg[ind].l = upd(seg[ind].l, s, mid, pos);
else seg[ind].r = upd(seg[ind].r, mid, e, pos);
seg[ind].x = seg[seg[ind].l].x + seg[seg[ind].r].x;
return ind;
}
int qr(int ind, int s, int e, int l, int r)
{
if(e <= l || r <= s) return 0;
if(l <= s && e <= r) return seg[ind].x;
int mid = s + e >> 1;
return qr(seg[ind].l, s, mid, l, r) + qr(seg[ind].r, mid, e, l, r);
}
vector<int> V;
void qry(int ind1, int ind2, int s, int e, int l, int r)
{
if(e <= l || r <= s || seg[ind1].x == seg[ind2].x) return;
if(s + 1 == e) { V.push_back(s); return; }
int mid = s + e >> 1;
qry(seg[ind1].l, seg[ind2].l, s, mid, l, r);
qry(seg[ind1].r, seg[ind2].r, mid, e, l, r);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
pii A[n]; for(auto &i : A) cin >> i.ff >> i.ss;
pii B[n], C[n];
for(int i = 0; i < n; ++i) B[i] = {A[i].ff + A[i].ss, i}, C[i] = {A[i].ff - A[i].ss, i};
sort(B, B + n);
sort(C, C + n);
int X[n], Y[n];
for(int i = 0; i < n; ++i) X[i] = B[i].ff, Y[i] = C[i].ff;
int P[n]; for(int i = 0; i < n; ++i) P[B[i].ss] = i;
int Q[n]; for(int i = 0; i < n; ++i) Q[i] = P[C[i].ss];
int R[n]; for(int i = 0; i < n; ++i) R[Q[i]] = i;
int root[n + 1];
root[0] = init(0, n);
for(int i = 0; i < n; ++i) root[i + 1] = upd(root[i], 0, n, Q[i]);
long long s = 0, e = 2ll * INF;
while(s + 1 < e)
{
int mid = ((long long)s + e) / 2;
long long ans = 0;
for(int i = 0; i < n; ++i)
{
int x = lower_bound(Y, Y + n, (int)max((long long)Y[i] - mid, (long long)-INF)) - Y;
int y = upper_bound(Y, Y + n, (int)min((long long)Y[i] + mid, (long long)INF)) - Y;
int l = lower_bound(X, X + n, (int)max((long long)X[Q[i]] - mid, (long long)-INF)) - X;
int r = upper_bound(X, X + n, (int)min((long long)X[Q[i]] + mid, (long long)INF)) - X;
ans += qr(root[y], 0, n, l, r) - qr(root[x], 0, n, l, r);
}
if(ans < n + 2 * k) s = mid;
else e = mid;
}
vector<int> ans;
for(int i = 0; i < n; ++i)
{
int x = lower_bound(Y, Y + n, (int)max((long long)Y[i] - s, (long long)-INF)) - Y;
int y = upper_bound(Y, Y + n, (int)min((long long)Y[i] + s, (long long)INF)) - Y;
int l = lower_bound(X, X + n, (int)max((long long)X[Q[i]] - s, (long long)-INF)) - X;
int r = upper_bound(X, X + n, (int)min((long long)X[Q[i]] + s, (long long)INF)) - X;
qry(root[x], root[y], 0, n, l, r);
// for(auto j : V) cout << j << ' '; cout << endl;
for(auto j : V) ans.push_back(max(abs(X[j] - X[Q[i]]), abs(Y[i] - Y[R[j]])));
V.clear();
}
while((int)ans.size() < n + 2 * k) ans.push_back(e);
sort(ans.begin(), ans.end());
for(int i = n; i < n + 2 * k; i += 2) cout << ans[i] << '\n';
}
Compilation message
road_construction.cpp: In function 'int init(int, int)':
road_construction.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = s + e >> 1;
| ~~^~~
road_construction.cpp: In function 'int upd(int, int, int, int)':
road_construction.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = s + e >> 1;
| ~~^~~
road_construction.cpp: In function 'int qr(int, int, int, int, int)':
road_construction.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int mid = s + e >> 1;
| ~~^~~
road_construction.cpp: In function 'void qry(int, int, int, int, int, int)':
road_construction.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
111 ms |
5168 KB |
Output is correct |
| 3 |
Execution timed out |
10095 ms |
332 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5506 ms |
77916 KB |
Output is correct |
| 2 |
Correct |
5189 ms |
77752 KB |
Output is correct |
| 3 |
Correct |
85 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
5335 ms |
77752 KB |
Output is correct |
| 5 |
Correct |
5508 ms |
77872 KB |
Output is correct |
| 6 |
Correct |
5627 ms |
77784 KB |
Output is correct |
| 7 |
Correct |
5459 ms |
77752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10097 ms |
73436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10097 ms |
73436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
111 ms |
5168 KB |
Output is correct |
| 3 |
Execution timed out |
10095 ms |
332 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
111 ms |
5168 KB |
Output is correct |
| 3 |
Execution timed out |
10095 ms |
332 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
