cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/joi2008ho_e.test.cpp

Depends on

Code

// #define PROBLEM "https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * 第7回日本情報オリンピック本選 (過去問) E - ペンキの色
 * https://atcoder.jp/contests/joi2008ho/submissions/71932516
 */

#include "../../Src/Sequence/CompressedSequence.hpp"
#include "../../Src/Algebra/Group/AdditiveGroup.hpp"
#include "../../Src/DataStructure/PrefixSum/Imos2D.hpp"

#include <iostream>
#include <cassert>

namespace zawa {}
using namespace zawa;
using namespace std;
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int W, H, N;
    cin >> W >> H >> N;
    vector<int> xs{0, W - 1}, ys{0, H - 1};
    vector<tuple<int, int, int, int>> ita(N);
    for (auto& [l, d, r, u] : ita) {
        cin >> l >> d >> r >> u;
        xs.push_back(l);
        if (r < W)
            xs.push_back(r);
        ys.push_back(d);
        if (u < H)
            ys.push_back(u);
    }
    CompressedSequence cx{xs}, cy{ys};
    Imos2D<AdditiveGroup<int>> imos(cx.size(), cy.size()); 
    for (auto [l, d, r, u] : ita) {
        imos.operation(cx[l], cy[d], cx[r], cy[u], 1);
    }
    auto solver = imos.inplaceBuild();
    vector id(cx.size(), vector<int>(cy.size(), -1));
    int ans = 0;
    for (int i = 0 ; i < ssize(cx) and cx.inverse(i) < W ; i++) 
        for (int j = 0 ; j < ssize(cy) and cy.inverse(j) < H ; j++) 
            if (id[i][j] == -1 and solver[i][j] == 0) {
                vector<pair<int, int>> que;
                que.emplace_back(i, j);
                ans++;
                for (int t = 0 ; t < ssize(que) ; t++) {
                    auto [x, y] = que[t];
                    if (x - 1 >= 0 and id[x - 1][y] == -1 and solver[x - 1][y] == 0) {
                        id[x - 1][y] = 1;
                        que.emplace_back(x - 1, y);
                    }
                    if (x + 1 < ssize(cx) and cx.inverse(x + 1) < W and id[x + 1][y] == -1 and solver[x + 1][y] == 0) {
                        id[x + 1][y] = 1;
                        que.emplace_back(x + 1, y);
                    }
                    if (y - 1 >= 0 and id[x][y - 1] == -1 and solver[x][y - 1] == 0) {
                        id[x][y - 1] = 1;
                        que.emplace_back(x, y - 1);
                    }
                    if (y + 1 < ssize(cy) and cy.inverse(y + 1) < H and id[x][y + 1] == -1 and solver[x][y + 1] == 0) {
                        id[x][y + 1] = 1;
                        que.emplace_back(x, y + 1);
                    }
                }
            }
    cout << ans << '\n';
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/joi2008ho_e.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * 第7回日本情報オリンピック本選 (過去問) E - ペンキの色
 * https://atcoder.jp/contests/joi2008ho/submissions/71932516
 */

#line 2 "Src/Sequence/CompressedSequence.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/CompressedSequence.hpp"

#include <vector>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
#line 2 "Src/Algebra/Group/AdditiveGroup.hpp"

namespace zawa {

template <class T>
class AdditiveGroup {
public:
    using Element = T;
    static constexpr T identity() noexcept {
        return T{};
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        return l + r;
    }
    static constexpr T inverse(const T& v) noexcept {
        return -v;
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/PrefixSum/Imos2D.hpp"

#line 2 "Src/Algebra/Group/GroupConcept.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 4 "Src/Algebra/Group/GroupConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Inversible = requires {
    typename T::Element;
    { T::inverse(std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

template <class T>
concept Group = Monoid<T> and Inversible<T>;

} // namespace Concept

} // namespace zawa
#line 5 "Src/DataStructure/PrefixSum/Imos2D.hpp"

#line 7 "Src/DataStructure/PrefixSum/Imos2D.hpp"
#include <utility>
#line 9 "Src/DataStructure/PrefixSum/Imos2D.hpp"

namespace zawa {

namespace internal {

template <concepts::Group G>
class StaticRectAddSolver {
public:
    
    using T = typename G::Element;

    using const_iterator = typename std::vector<std::vector<T>>::const_iterator;

    explicit StaticRectAddSolver(const std::vector<std::vector<T>>& imos) : m_H{imos.size() - 1}, m_W{imos[0].size() - 1}, m_a(imos) {
        build();
    }

    explicit StaticRectAddSolver(std::vector<std::vector<T>>&& imos) : m_H{imos.size() - 1}, m_W{imos[0].size() - 1}, m_a{std::move(imos)} {
        build();
    }

    inline usize size() const {
        return m_H;
    }

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    const_iterator begin() const {
        return m_a.begin();
    }

    const_iterator end() const {
        return m_a.end();
    }

    const std::vector<T>& operator[](usize i) const {
        assert(i < height() and "invalid access m_sum[i]: StaticRectSumSolver::operator[]");
        return m_a[i];
    }

private:

    usize m_H, m_W;

    std::vector<std::vector<T>> m_a;

    void build() {
        for (usize i = 0 ; i < m_H ; i++)
            for (usize j = 1 ; j <= m_W ; j++)
                m_a[i][j] = G::operation(m_a[i][j], m_a[i][j - 1]);
        for (usize i = 1 ; i <= m_H ; i++)
            for (usize j = 0 ; j < m_W ; j++)
                m_a[i][j] = G::operation(m_a[i][j], m_a[i - 1][j]);
    }
};

} // namespace internal

template <concepts::Group G>
class Imos2D {
public:
    
    using T = typename G::Element;

    Imos2D(usize H, usize W) : m_H{H}, m_W{W}, m_imos(H + 1, std::vector<T>(W + 1, G::identity())) {}

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    // [l, r) x [d, u)
    void operation(usize l, usize d, usize r, usize u, T v) {
        assert((l <= r and r <= height()) and "invalid i range: Imos2D::add");
        assert((d <= u and u <= width()) and "invalid j range: Imos2D::add");
        assert(m_moved == false and "data is already builded: Imos2D::add");
        T inv = G::inverse(v);
        m_imos[l][d] = G::operation(m_imos[l][d], v);
        m_imos[l][u] = G::operation(m_imos[l][u], inv);
        m_imos[r][d] = G::operation(m_imos[r][d], inv);
        m_imos[r][u] = G::operation(m_imos[r][u], v);
    }

    const std::vector<T>& operator[](const usize i) const {
        assert(m_moved == false and "data is already builded: Imos2D::operator[]");
        assert(i < height() and "invalid range: Imos2D::operator[]");
        return m_imos[i];
    }

    internal::StaticRectAddSolver<G> build() const {
        assert(m_moved == false and "data is already builded: Imos2D::build");
        return internal::StaticRectAddSolver<G>{m_imos};
    }

    internal::StaticRectAddSolver<G> inplaceBuild() {
        assert(m_moved == false and "data is already builded: Imos2D::build");
        m_moved = true;
        return internal::StaticRectAddSolver<G>{std::move(m_imos)};
    }

private:

    usize m_H = 0, m_W = 0;

    std::vector<std::vector<T>> m_imos;

    bool m_moved = false;
};

} // namespace zawa
#line 12 "Test/AtCoder/joi2008ho_e.test.cpp"

#include <iostream>
#line 15 "Test/AtCoder/joi2008ho_e.test.cpp"

namespace zawa {}
using namespace zawa;
using namespace std;
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int W, H, N;
    cin >> W >> H >> N;
    vector<int> xs{0, W - 1}, ys{0, H - 1};
    vector<tuple<int, int, int, int>> ita(N);
    for (auto& [l, d, r, u] : ita) {
        cin >> l >> d >> r >> u;
        xs.push_back(l);
        if (r < W)
            xs.push_back(r);
        ys.push_back(d);
        if (u < H)
            ys.push_back(u);
    }
    CompressedSequence cx{xs}, cy{ys};
    Imos2D<AdditiveGroup<int>> imos(cx.size(), cy.size()); 
    for (auto [l, d, r, u] : ita) {
        imos.operation(cx[l], cy[d], cx[r], cy[u], 1);
    }
    auto solver = imos.inplaceBuild();
    vector id(cx.size(), vector<int>(cy.size(), -1));
    int ans = 0;
    for (int i = 0 ; i < ssize(cx) and cx.inverse(i) < W ; i++) 
        for (int j = 0 ; j < ssize(cy) and cy.inverse(j) < H ; j++) 
            if (id[i][j] == -1 and solver[i][j] == 0) {
                vector<pair<int, int>> que;
                que.emplace_back(i, j);
                ans++;
                for (int t = 0 ; t < ssize(que) ; t++) {
                    auto [x, y] = que[t];
                    if (x - 1 >= 0 and id[x - 1][y] == -1 and solver[x - 1][y] == 0) {
                        id[x - 1][y] = 1;
                        que.emplace_back(x - 1, y);
                    }
                    if (x + 1 < ssize(cx) and cx.inverse(x + 1) < W and id[x + 1][y] == -1 and solver[x + 1][y] == 0) {
                        id[x + 1][y] = 1;
                        que.emplace_back(x + 1, y);
                    }
                    if (y - 1 >= 0 and id[x][y - 1] == -1 and solver[x][y - 1] == 0) {
                        id[x][y - 1] = 1;
                        que.emplace_back(x, y - 1);
                    }
                    if (y + 1 < ssize(cy) and cy.inverse(y + 1) < H and id[x][y + 1] == -1 and solver[x][y + 1] == 0) {
                        id[x][y + 1] = 1;
                        que.emplace_back(x, y + 1);
                    }
                }
            }
    cout << ans << '\n';
#else
    cout << "Hello World\n";
#endif
}
Back to top page