cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/graph/segment_tree_graph/flags.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/arc069/tasks/arc069_f"

#include <algorithm>
#include <iostream>
#include <numeric>
#include <atcoder/twosat>

#include "library/graph/segment_tree_graph.hpp"
using namespace suisen;

int main() {
    int n;
    std::cin >> n;

    std::vector xys(2, std::vector<long long>(n));
    for (int i = 0; i < n; ++i) {
        std::cin >> xys[0][i] >> xys[1][i];
    }

    SegmentTreeGraph g(n);

    std::vector ps(2, std::vector<int>(n));
    for (int t = 0; t < 2; ++t) {
        std::iota(ps[t].begin(), ps[t].end(), 0);
        std::sort(ps[t].begin(), ps[t].end(), [&](int i, int j) { return xys[t][i] < xys[t][j]; });
        g.add_order(ps[t]);
    }

    auto get_range = [&](int order_id, long long c, long long d) -> std::pair<int, int> {
        const auto &p = ps[order_id];
        const auto &a = xys[order_id];
        auto bs = [&](long long x) {
            int l = -1, r = n;
            while (r - l > 1) {
                int m = (l + r) >> 1;
                (a[p[m]] < x ? l : r) = m;
            }
            return r;
        };
        return { bs(c - d + 1), bs(c + d) };
    };

    auto check = [&](const long long d) -> bool {
        atcoder::two_sat sat(g.size());

        g.add_edges_to_children(
            [&](int p, int c) {
                assert(g.is_segment_node(p));
                bool b = g.get_segment_node(p).order_id == 0;
                sat.add_clause(c, b, p, not b);
            }
        );

        for (int i = 0; i < n; ++i) {
            for (auto jk : std::vector<std::pair<int, int>> { { 0, 0 }, { 0, 1 }, { 1, 1 } }) {
                const int j = jk.first, k = jk.second, p = ps[j][i];
                auto [l, r] = get_range(k, xys[j][p], d);
                if (j == k) r = i;
                g.add_edge(p, { k, l, r }, [&](int fr, int to) { sat.add_clause(fr, j ^ 1, to, k ^ 1); });
            }
        }

        return sat.satisfiable();
    };

    long long l = 0, r = 1000000001;
    while (r - l > 1) {
        long long d = (l + r) >> 1;
        (check(d) ? l : r) = d;
    }
    std::cout << l << std::endl;

    return 0;
}
#line 1 "test/src/graph/segment_tree_graph/flags.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/arc069/tasks/arc069_f"

#include <algorithm>
#include <iostream>
#include <numeric>
#include <atcoder/twosat>

#line 1 "library/graph/segment_tree_graph.hpp"



#include <cassert>
#include <type_traits>
#include <vector>

namespace suisen {

class SegmentTreeGraph {
    public:
        struct SegmentNode { const int order_id, l, r; };

        SegmentTreeGraph() : SegmentTreeGraph(0) {}
        SegmentTreeGraph(int n) : n(n), next_id(n), ceil_log2(n + 2, 0), is_invalid_node(n, false) {
            for (int i = 1, l = 0; i <= n + 1; ++i) {
                ceil_log2[i] = l;
                l += (i & -i) == i;
            }
            if (n) {
                for (int m = n / (-n & n) >> 1;; m >>= 1) {
                    is_invalid_node[m] = true;
                    if (m == 0) break;
                }
            }
        }

        int size() const {
            return next_id;
        }

        int add_order(const std::vector<int> &p) {
            assert(int(p.size()) == n);
            std::vector<int> seg(2 * n, -1);
            for (int i = 0; i < n; ++i) seg[n + i] = p[i];
            for (int i = 1; i < n; ++i) seg[i] = next_id++;
            segs.push_back(std::move(seg));
            return segs.size() - 1;
        }
        int add_order_identity() {
            std::vector<int> p(n);
            for (int i = 0; i < n; ++i) p[i] = i;
            return add_order(p);
        }

        bool is_segment_node(int node_id) const {
            return node_id >= n;
        }

        SegmentNode get_segment_node(int node_id) const {
            assert(node_id >= n);
            node_id -= n;
            int order_id = node_id / (n - 1);
            int k = node_id - order_id * (n - 1) + 1;
            int l = k << ceil_log2[(n + k - 1) / k], r = (k + 1) << ceil_log2[n / (k + 1) + 1];
            return SegmentNode { order_id, l - n, r - n };
        }
        SegmentNode operator[](int node_id) const {
            return get_segment_node(node_id);
        }

        // add_edge(parent, child_l, child_r)
        template <typename AddEdge, std::enable_if_t<std::is_invocable_v<AddEdge, int, int, int>, std::nullptr_t> = nullptr>
        void add_edges_to_children(AddEdge add_edge) {
            for (const auto &seg : segs) {
                for (int i = 1; i < n; ++i) {
                    if (is_invalid_node[i]) continue;
                    add_edge(seg[i], seg[i * 2 + 0], seg[i * 2 + 1]);
                }
            }
        }
        // add_edge(parent, child)
        template <typename AddEdge, std::enable_if_t<std::is_invocable_v<AddEdge, int, int>, std::nullptr_t> = nullptr>
        void add_edges_to_children(AddEdge add_edge) {
            for (const auto &seg : segs) {
                for (int i = 1; i < n; ++i) {
                    if (is_invalid_node[i]) continue;
                    add_edge(seg[i], seg[i * 2 + 0]);
                    add_edge(seg[i], seg[i * 2 + 1]);
                }
            }
        }

        // add_edge(from, to)
        template <typename AddEdge, std::enable_if_t<std::is_invocable_v<AddEdge, int, int>, std::nullptr_t> = nullptr>
        void add_edge(int from, SegmentNode to, AddEdge add_edge_func) {
            const auto &seg = segs[to.order_id];
            for (int lk = to.l + n, rk = to.r + n; lk < rk; lk >>= 1, rk >>= 1) {
                if (lk & 1) add_edge_func(from, seg[lk++]);
                if (rk & 1) add_edge_func(from, seg[--rk]);
            }
        }

    private:
        int n;
        int next_id;
        std::vector<int> ceil_log2;
        std::vector<char> is_invalid_node;
        std::vector<std::vector<int>> segs;
};

} // namespace suisen



#line 9 "test/src/graph/segment_tree_graph/flags.test.cpp"
using namespace suisen;

int main() {
    int n;
    std::cin >> n;

    std::vector xys(2, std::vector<long long>(n));
    for (int i = 0; i < n; ++i) {
        std::cin >> xys[0][i] >> xys[1][i];
    }

    SegmentTreeGraph g(n);

    std::vector ps(2, std::vector<int>(n));
    for (int t = 0; t < 2; ++t) {
        std::iota(ps[t].begin(), ps[t].end(), 0);
        std::sort(ps[t].begin(), ps[t].end(), [&](int i, int j) { return xys[t][i] < xys[t][j]; });
        g.add_order(ps[t]);
    }

    auto get_range = [&](int order_id, long long c, long long d) -> std::pair<int, int> {
        const auto &p = ps[order_id];
        const auto &a = xys[order_id];
        auto bs = [&](long long x) {
            int l = -1, r = n;
            while (r - l > 1) {
                int m = (l + r) >> 1;
                (a[p[m]] < x ? l : r) = m;
            }
            return r;
        };
        return { bs(c - d + 1), bs(c + d) };
    };

    auto check = [&](const long long d) -> bool {
        atcoder::two_sat sat(g.size());

        g.add_edges_to_children(
            [&](int p, int c) {
                assert(g.is_segment_node(p));
                bool b = g.get_segment_node(p).order_id == 0;
                sat.add_clause(c, b, p, not b);
            }
        );

        for (int i = 0; i < n; ++i) {
            for (auto jk : std::vector<std::pair<int, int>> { { 0, 0 }, { 0, 1 }, { 1, 1 } }) {
                const int j = jk.first, k = jk.second, p = ps[j][i];
                auto [l, r] = get_range(k, xys[j][p], d);
                if (j == k) r = i;
                g.add_edge(p, { k, l, r }, [&](int fr, int to) { sat.add_clause(fr, j ^ 1, to, k ^ 1); });
            }
        }

        return sat.satisfiable();
    };

    long long l = 0, r = 1000000001;
    while (r - l > 1) {
        long long d = (l + r) >> 1;
        (check(d) ? l : r) = d;
    }
    std::cout << l << std::endl;

    return 0;
}
Back to top page