oj.uz

답안 #998130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998130 2024-06-13T10:16:37 Z Qwerty1232 Izvanzemaljci (COI21_izvanzemaljci) C++17
26 / 100
 167 ms 21780 KB 
#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++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -