Submission #998130

#	Time	Username	Problem	Language	Result	Execution time	Memory
998130		Qwerty1232	Izvanzemaljci (COI21_izvanzemaljci)	C++17	26 / 100	167 ms	21780 KiB

izvanzemaljci

#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 (stderr)

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++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32