#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;
struct SegTree{
ll cnt = 0;
struct Node{
vector <ll> V;
ll chl = -1;
ll chr = -1;
};
vector <Node> st;
void get(ll &id) {
if (id == -1) {
st.push_back({{}, -1, -1});
id = ++cnt;
}
}
void add(ll &id, ll l, ll r, ll x, ll y) {
get(id);
if (l == r) {
st[id].V.push_back(y);
return;
}
ll mid = (l+r)/2;
if (x <= mid) {
ll tmp = st[id].chl;
add(tmp, l, mid, x, y);
st[id].chl = tmp;
}
else {
ll tmp = st[id].chr;
add(tmp, mid+1, r, x, y);
st[id].chr = tmp;
}
}
void build(ll id, ll l, ll r) {
if (st[id].chl == -1 && st[id].chr == -1) {
sort(st[id].V.begin(), st[id].V.end());
return;
}
ll mid = (l+r)/2;
if (st[id].chr == -1) {
build(st[id].chl, l, mid);
st[id].V = st[st[id].chl].V;
}
else if (st[id].chl == -1) {
build(st[id].chr, mid+1, r);
st[id].V = st[st[id].chr].V;
}
else {
build(st[id].chl, l, mid);
build(st[id].chr, mid+1, r);
int i = 0, j = 0;
while (i < st[st[id].chl].V.size() && j < st[st[id].chr].V.size()) {
if (st[st[id].chl].V[i] <= st[st[id].chr].V[j]) st[id].V.push_back(st[st[id].chl].V[i++]);
else st[id].V.push_back(st[st[id].chr].V[j++]);
}
while (i < st[st[id].chl].V.size()) st[id].V.push_back(st[st[id].chl].V[i++]);
while (j < st[st[id].chr].V.size()) st[id].V.push_back(st[st[id].chr].V[j++]);
}
}
ll query(ll id, ll l, ll r, ll xl, ll xr, ll yl, ll yr) {
if (id == -1 || xr < l || r < xl) return 0;
else if (xl <= l && r <= xr) {
auto itL = lower_bound(st[id].V.begin(), st[id].V.end(), yl);
auto itR = lower_bound(st[id].V.begin(), st[id].V.end(), yr+1);
return itR-itL;
}
ll mid = (l+r)/2;
return query(st[id].chl, l, mid, xl, xr, yl, yr) + query(st[id].chr, mid+1, r, xl, xr, yl, yr);
}
}ST;
ll n, f, k, x, l = 0, rt, r = 4e9, mid;
array <ll, 2> A[250000];
void solve(ll u) {
f = 0;
for (int i=0; i<n; ++i) {
f += ST.query(rt, 0LL, (ll)4e9, max(0LL, A[i][0]+A[i][1]-u), min((ll)4e9, A[i][0]+A[i][1]+u), A[i][0]-A[i][1]-u, A[i][0]-A[i][1]+u);
}
f -= n;
f /= 2;
}
void dnc(ll l, ll r, ll ql, ll qr) {
if (l == r) {
for (int i=ql; i<=qr; ++i) cout << l << '\n';
return;
}
ll mid = (l+r)/2;
solve(mid);
ll tmp = f;
if (tmp && tmp != ql) dnc(l, mid, ql, tmp);
if (tmp < qr) dnc(mid+1, r, tmp, qr);
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
ST.st.push_back({{}, -1, -1});
cin >> n >> k;
for (int i=0; i<n; ++i) {
cin >> A[i][0] >> A[i][1];
A[i][0] += (ll)1e9, A[i][1] += (ll)1e9;
ST.add(rt, 0LL, (ll)4e9, A[i][0]+A[i][1], A[i][0]-A[i][1]);
}
ST.build(rt, 0LL, (ll)4e9);
dnc(0, (ll)4e9, 1, k);
}
Compilation message
road_construction.cpp: In member function 'void SegTree::build(long long int, long long int, long long int)':
road_construction.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | while (i < st[st[id].chl].V.size() && j < st[st[id].chr].V.size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:59:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | while (i < st[st[id].chl].V.size() && j < st[st[id].chr].V.size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | while (i < st[st[id].chl].V.size()) st[id].V.push_back(st[st[id].chl].V[i++]);
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | while (j < st[st[id].chr].V.size()) st[id].V.push_back(st[st[id].chr].V[j++]);
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10005 ms |
2228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10020 ms |
294796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10055 ms |
311772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10055 ms |
311772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10005 ms |
2228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10005 ms |
2228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
