#include <bits/stdc++.h>
#define int int64_t
template <class cmp>
struct ST {
std::vector<int> data;
int size;
ST() = default;
void build(const std::vector<int>& input) {
size = 1 << std::__lg(std::max<int64_t>(1, (int)input.size() - 1)) + 1;
data.assign(size * 2, 0);
std::copy(input.begin(), input.end(), data.begin() + size);
for (int i = size - 1; i > 0; i--) {
data[i] = std::min(data[2 * i], data[2 * i + 1], cmp());
}
}
int get(int l, int r) {
assert(l < r);
int res = data[l + size];
for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
if (l & 1)
res = std::min(res, data[l++], cmp());
if (r & 1)
res = std::min(res, data[--r], cmp());
}
return res;
}
};
auto cmp_cum = [](auto a, auto b) {
int mx1 = 0;
int mx2 = 0;
for (int i = 0; i < a.size(); i++) {
mx1 = std::max(mx1, a[i][2]);
}
for (int i = 0; i < b.size(); i++) {
mx2 = std::max(mx2, b[i][2]);
}
return mx1 < mx2;
};
struct Cum {
std::vector<std::pair<int, int>> data;
std::vector<int> ord_x, ord_y, ord_x_val, ord_y_val;
std::vector<int> all_x, all_y;
ST<std::less<>> st_min_x, st_min_y;
ST<std::greater<>> st_max_x, st_max_y;
int n;
Cum(const std::vector<std::pair<int, int>>& data) : data(data) {
n = data.size();
for (auto [x, y] : data) {
all_x.push_back(x);
all_y.push_back(y);
}
std::sort(all_x.begin(), all_x.end());
std::sort(all_y.begin(), all_y.end());
ord_x_val = all_x;
ord_y_val = all_y;
all_x.erase(std::unique(all_x.begin(), all_x.end()), all_x.end());
all_y.erase(std::unique(all_y.begin(), all_y.end()), all_y.end());
ord_x.resize(n);
ord_y.resize(n);
std::iota(ord_x.begin(), ord_x.end(), 0);
std::iota(ord_y.begin(), ord_y.end(), 0);
std::sort(ord_x.begin(), ord_x.end(), [&](int a, int b) { return data[a].first < data[b].first; });
std::sort(ord_y.begin(), ord_y.end(), [&](int a, int b) { return data[a].second < data[b].second; });
std::vector<int> vec_x(n), vec_y(n);
for (int i = 0; i < n; i++) {
vec_y[i] = data[ord_x[i]].second;
vec_x[i] = data[ord_y[i]].first;
}
st_min_x.build(vec_x);
st_max_x.build(vec_x);
st_min_y.build(vec_y);
st_max_y.build(vec_y);
}
std::array<int, 3> get_prf_x(int i) {
if (i == -1) {
return {-1, -1, -1};
}
int x_id = std::upper_bound(ord_x_val.begin(), ord_x_val.end(), all_x[i]) - ord_x_val.begin() - 1;
int min_x = data[ord_x[0]].first;
int max_x = data[ord_x[x_id]].first;
int min_y = st_min_y.get(0, x_id + 1);
int max_y = st_max_y.get(0, x_id + 1);
int s = std::max<int64_t>({1, max_x - min_x, max_y - min_y});
return {max_x - s, min_y, s};
}
std::array<int, 3> get_suf_x(int i) {
if (i == all_x.size()) {
return {-1, -1, -1};
}
int x_id = std::lower_bound(ord_x_val.begin(), ord_x_val.end(), all_x[i]) - ord_x_val.begin();
int min_x = data[ord_x[x_id]].first;
int max_x = data[ord_x[n - 1]].first;
int min_y = st_min_y.get(x_id, n);
int max_y = st_max_y.get(x_id, n);
int s = std::max<int64_t>({1, max_x - min_x, max_y - min_y});
return {min_x, min_y, s};
}
// std::array<int, 3> get_prf_y(int y_id) {
// if (y_id == n) {
// return {-1, -1, -1};
// }
// int min_x = st_min_x.get(0, y_id + 1);
// int max_x = st_max_x.get(0, y_id + 1);
//
// int min_y = data[ord_y[0]].first;
// int max_y = data[ord_y[y_id]].first;
//
// int s = std::max({1, max_x - min_x, max_y - min_y});
// return {max_x - s, max_y - s, s};
// }
// std::array<int, 3> get_suf_y(int y_id) {
// if (y_id == n) {
// return {-1, -1, -1};
// }
// int min_x = st_min_x.get(y_id, n);
// int max_x = st_max_x.get(y_id, n);
//
// int min_y = data[ord_y[y_id]].first;
// int max_y = data[ord_y[n - 1]].first;
//
// int s = std::max({1, max_x - min_x, max_y - min_y});
// return {min_x, min_y, s};
// }
std::array<std::array<int, 3>, 2> get_cum_x() {
// int beg = -1, end = all_x.size();
// while (beg + 1 < end) {
// int mid = (beg + end) / 2;
// if (get_prf_x(mid)[2] < get_suf_x(mid + 1)[2]) {
// beg = mid;
// } else {
// end = mid;
// }
// }
std::array<std::array<int, 3>, 2> ans = {{{-1, -1, int(2e9 + 5)}, {-1, -1, (int)2e9 + 5}}};
// if (beg != -1) {
// ans = std::min(ans, {get_prf_x(beg), get_suf_x(beg + 1)}, cmp_cum);
// }
// if (end != all_x.size()) {
// ans = std::min(ans, {get_prf_x(end), get_suf_x(end + 1)}, cmp_cum);
// }
for (int i = -1; i < (int)all_x.size(); i++) {
ans = std::min(ans, {get_prf_x(i), get_suf_x(i + 1)}, cmp_cum);
}
return ans;
}
};
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
std::vector<std::pair<int, int>> input(n);
for (auto& [x, y] : input) {
std::cin >> x >> y;
}
if (k == 1) {
int min_x = input[0].first, min_y = input[0].second;
int max_x = input[0].first, max_y = input[0].second;
for (auto [x, y] : input) {
min_x = std::min(min_x, x);
min_y = std::min(min_y, y);
max_x = std::max(max_x, x);
max_y = std::max(max_y, y);
}
std::cout << min_x << " " << min_y << " " << std::max<int64_t>({1, max_x - min_x, max_y - min_y}) << std::endl;
return 0;
}
if (k == 2) {
auto solve = [](std::vector<std::pair<int, int>> vec) {
Cum cum(vec);
auto ans = cum.get_cum_x();
return ans;
};
auto ans = solve(input);
auto input2 = input;
for (auto& [x, y] : input2) {
std::swap(x, y);
}
auto ans2 = solve(input2);
for (auto& [x, y, l] : ans2) {
std::swap(x, y);
}
ans = std::min(ans, ans2, cmp_cum);
int CUM = 2.99e9 - 100;
// int CUM = 3.01e9 - 100;
for (auto& [a, b, c] : ans) {
if (c == -1) {
a = b = CUM;
c = 1;
CUM += 10;
}
}
for (auto& [x, y] : input) {
int cnt = 0;
for (auto& [a, b, c] : ans) {
cnt += a <= x && x <= a + c && b <= y && y <= b + c;
}
assert(cnt >= 1);
}
for (int i = 0; i < ans.size(); i++) {
for (int j = i + 1; j < ans.size(); j++) {
auto& [a1, b1, c1] = ans[i];
auto& [a2, b2, c2] = ans[j];
if (!(a1 + c1 < a2 || a2 + c2 < a1 || b1 + c1 < b2 || b2 + c2 < b1)) {
assert(false && "squares intersect");
}
}
}
for (auto [a, b, c] : ans) {
std::cout << a << " " << b << " " << c << "\n";
}
std::cout.flush();
return 0;
}
return 0;
}
Compilation message
izvanzemaljci.cpp: In member function 'std::array<long int, 3> Cum::get_suf_x(int64_t)':
izvanzemaljci.cpp:105:15: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | if (i == all_x.size()) {
| ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In function 'int32_t main()':
izvanzemaljci.cpp:228:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::array<std::array<long int, 3>, 2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
228 | for (int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
izvanzemaljci.cpp:229:35: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::array<std::array<long int, 3>, 2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
229 | for (int j = i + 1; j < ans.size(); j++) {
| ~~^~~~~~~~~~~~
izvanzemaljci.cpp: In instantiation of 'void ST<cmp>::build(const std::vector<long int>&) [with cmp = std::less<void>]':
izvanzemaljci.cpp:84:29: required from here
izvanzemaljci.cpp:13:76: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
13 | size = 1 << std::__lg(std::max<int64_t>(1, (int)input.size() - 1)) + 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
izvanzemaljci.cpp: In instantiation of 'void ST<cmp>::build(const std::vector<long int>&) [with cmp = std::greater<void>]':
izvanzemaljci.cpp:85:29: required from here
izvanzemaljci.cpp:13:76: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
izvanzemaljci.cpp: In instantiation of '<lambda(auto:23, auto:24)> [with auto:23 = std::array<std::array<long int, 3>, 2>; auto:24 = std::array<std::array<long int, 3>, 2>]':
/usr/include/c++/10/bits/stl_algobase.h:281:17: required from 'constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare) [with _Tp = std::array<std::array<long int, 3>, 2>; _Compare = <lambda(auto:23, auto:24)>]'
izvanzemaljci.cpp:164:74: required from here
izvanzemaljci.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::array<std::array<long int, 3>, 2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
izvanzemaljci.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::array<std::array<long int, 3>, 2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i = 0; i < b.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
15 ms |
1880 KB |
Output is correct |
| 8 |
Correct |
15 ms |
2036 KB |
Output is correct |
| 9 |
Correct |
15 ms |
1884 KB |
Output is correct |
| 10 |
Correct |
15 ms |
2032 KB |
Output is correct |
| 11 |
Correct |
16 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
150 ms |
21620 KB |
Output is correct |
| 11 |
Correct |
145 ms |
21716 KB |
Output is correct |
| 12 |
Correct |
142 ms |
21568 KB |
Output is correct |
| 13 |
Correct |
148 ms |
21620 KB |
Output is correct |
| 14 |
Correct |
167 ms |
21616 KB |
Output is correct |
| 15 |
Correct |
158 ms |
21716 KB |
Output is correct |
| 16 |
Correct |
156 ms |
21768 KB |
Output is correct |
| 17 |
Correct |
148 ms |
20596 KB |
Output is correct |
| 18 |
Correct |
144 ms |
20344 KB |
Output is correct |
| 19 |
Correct |
134 ms |
18784 KB |
Output is correct |
| 20 |
Correct |
124 ms |
19320 KB |
Output is correct |
| 21 |
Correct |
158 ms |
21780 KB |
Output is correct |
| 22 |
Correct |
156 ms |
21716 KB |
Output is correct |
| 23 |
Correct |
151 ms |
21776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
