/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define int long long
#define isz(x) (int)x.size()
using namespace std;
template<class B, class T>
struct fenwick_tree_2d_sparse_sum{
vector<B> X;
vector<vector<array<B, 2>>> Y;
vector<vector<T>> data;
// O(n * log^2(n))
fenwick_tree_2d_sparse_sum(vector<pair<array<B, 2>, T>> init): X(init.size()){
sort(init.begin(), init.end());
for(auto i = 0; i < (int)init.size(); ++ i) X[i] = init[i].first[0];
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
int n = (int)X.size();
Y.resize(n);
data.resize(n);
vector<vector<pair<array<B, 2>, T>>> hold(n);
for(auto i = 0, x = 0; i < (int)init.size(); ++ i){
auto [pos, val] = init[i];
while(X[x] < pos[0]) ++ x;
hold[x].push_back({{pos[1], pos[0]}, val});
}
for(auto x = 1; x <= n; ++ x) if(x + (x & -x) <= n){
auto &hold0 = hold[x + (x & -x) - 1];
auto &hold1 = hold[x - 1];
int size = (int)hold0.size();
hold0.insert(hold0.end(), hold1.begin(), hold1.end());
}
for(auto x = 0; x < n; ++ x){
auto &Y0 = Y[x];
auto &hold0 = hold[x];
auto &data0 = data[x];
sort(hold0.begin(), hold0.end());
Y0.resize(hold0.size());
for(auto j = 0; j < (int)hold0.size(); ++ j) Y0[j] = hold0[j].first;
Y0.erase(unique(Y0.begin(), Y0.end()), Y0.end());
data0.resize(Y0.size());
for(auto j = 0, y = 0; j < (int)hold0.size(); ++ j){
while(Y0[y] < hold0[j].first) ++ y;
data0[y] += hold0[j].second;
}
int m = (int)data0.size();
for(auto y = 1; y <= m; ++ y) if(y + (y & -y) <= m) data0[y + (y & -y) - 1] += data0[y - 1];
}
}
// O(log^2(n))
void update(B _p, B _q, T x){
int p = lower_bound(X.begin(), X.end(), _p) - X.begin();
assert(p < (int)X.size() && X[p] == _p);
for(auto i = p + 1; i <= (int)X.size(); i += i & -i){
auto &Y0 = Y[i - 1];
auto &data0 = data[i - 1];
int q = lower_bound(Y0.begin(), Y0.end(), array{_q, _p}) - Y0.begin();
assert(q < (int)Y0.size() && Y0[q][0] == _q && Y0[q][1] == _p);
for(auto j = q + 1; j <= (int)data0.size(); j += j & -j) data0[j - 1] += x;
}
}
// O(log^2(n))
T prefix(B _xr, B _yr) const{
int xr = lower_bound(X.begin(), X.end(), _xr) - X.begin();
T res = 0;
for(auto i = xr; i > 0; i -= i & -i){
auto &Y0 = Y[i - 1];
auto &data0 = data[i - 1];
int yr = lower_bound(Y0.begin(), Y0.end(), array{_yr, numeric_limits<B>::min()}) - Y0.begin();
for(auto j = yr; j > 0; j -= j & -j) res += data0[j - 1];
}
return res;
}
// O(log^2(n))
T query(B _xl, B _xr, B _yl, B _yr) const{
return prefix(_xr, _yr) - prefix(_xl, _yr) - prefix(_xr, _yl) + prefix(_xl, _yl);
}
// O(log^2(n))
T query(B _x, B _y) const{
return prefix(_x + 1, _y + 1) - prefix(_x + 1, _y) - prefix(_x, _y + 1) + prefix(_x, _y);
}
};
void solve() {
int n, k;
cin >> n >> k;
vector<pair<int, int>> vec;
vector<pair<array<int, 2>, int>> pre_needed;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
vec.emplace_back(x + y, x - y);
pre_needed.push_back({{x + y, x - y}, 1});
// cout << x + y << " " << x - y << endl;
}
sort(all(vec));
fenwick_tree_2d_sparse_sum BIT2D(pre_needed);
auto query = [&](int val) {
int res = 0;
for (auto [x, y] : vec) {
res += BIT2D.query(x - val, x + val + 1, y - val, y + val + 1) - 1;
}
return res / 2;
};
int l = 0, r = 4e9;
while (l < r) {
int mid = (l + r) >> 1;
if (query(mid) >= k) r = mid;
else l = mid + 1;
}
auto dis = [&](const auto &A, const auto &B) -> int {
return max(abs(A.first - B.second), abs(A.second - B.first));
};
int lim = l - 1;
int ptr = 0, ptr2 = 0;
map<int, int> mp;
set<pair<int, int>> s;
for (int i = 0; i < n; ++i) {
// cout << i << ": " << vec[i].first << " " << vec[i].second << endl;
while (ptr2 < n and vec[i].first - vec[ptr2].first > lim) {
auto val = vec[ptr2];
// cout << "- " << val.first << " " << val.second << endl;
swap(val.first, val.second);
s.erase(val);
++ptr2;
}
while (ptr < n and vec[ptr].first <= vec[i].first + lim) {
auto val = vec[ptr];
// cout << "+ " << val.first << " " << val.second << endl;
swap(val.first, val.second);
s.insert(val);
++ptr;
}
for (auto it = s.lower_bound(pair<int, int>{vec[i].second - lim, -1}); it != s.end() and it->first <= vec[i].second + lim; it = next(it)) {
// cout << it->second << " " << it->first << endl;
mp[dis(vec[i], *it)]++;
}
// cout << endl;
}
for (auto [val, cnt] : mp) if (val) {
k -= cnt / 2;
for (int i = 0; i < cnt / 2; ++i) cout << val << "\n";
}
for (int i = 0; i < k; ++i) cout << l << "\n";
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
cout << "Check array size pls sir" << endl;
#endif
}
Compilation message
road_construction.cpp: In instantiation of 'fenwick_tree_2d_sparse_sum<B, T>::fenwick_tree_2d_sparse_sum(std::vector<std::pair<std::array<B, 2>, T> >) [with B = long long int; T = long long int]':
road_construction.cpp:107:48: required from here
road_construction.cpp:38:17: warning: unused variable 'size' [-Wunused-variable]
38 | int size = (int)hold0.size();
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
18796 KB |
Output is correct |
| 2 |
Correct |
192 ms |
18912 KB |
Output is correct |
| 3 |
Correct |
191 ms |
18896 KB |
Output is correct |
| 4 |
Correct |
212 ms |
19028 KB |
Output is correct |
| 5 |
Correct |
113 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
8 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5722 ms |
158840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10107 ms |
159784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10107 ms |
159784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
18796 KB |
Output is correct |
| 2 |
Correct |
192 ms |
18912 KB |
Output is correct |
| 3 |
Correct |
191 ms |
18896 KB |
Output is correct |
| 4 |
Correct |
212 ms |
19028 KB |
Output is correct |
| 5 |
Correct |
113 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
8 ms |
604 KB |
Output is correct |
| 7 |
Correct |
6445 ms |
63556 KB |
Output is correct |
| 8 |
Correct |
6022 ms |
63812 KB |
Output is correct |
| 9 |
Correct |
189 ms |
19024 KB |
Output is correct |
| 10 |
Correct |
4852 ms |
64176 KB |
Output is correct |
| 11 |
Correct |
4381 ms |
62124 KB |
Output is correct |
| 12 |
Correct |
1922 ms |
33608 KB |
Output is correct |
| 13 |
Correct |
1812 ms |
39276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
18796 KB |
Output is correct |
| 2 |
Correct |
192 ms |
18912 KB |
Output is correct |
| 3 |
Correct |
191 ms |
18896 KB |
Output is correct |
| 4 |
Correct |
212 ms |
19028 KB |
Output is correct |
| 5 |
Correct |
113 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
8 ms |
604 KB |
Output is correct |
| 7 |
Incorrect |
5722 ms |
158840 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
