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/abc434_d.test.cpp

Depends on

Code

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

/*
 * AtCoder Beginner Contest 434 D - Clouds
 * https://atcoder.jp/contests/abc434/submissions/71932493
 */

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

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
using namespace zawa;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
#ifdef ATCODER
    const int MAX = 2000;
    int N;
    cin >> N;
    Imos2D<AdditiveGroup<int>> imos(MAX, MAX);
    vector<tuple<int, int, int, int>> A(N);
    for (auto& [l, r, d, u] : A) {
        cin >> l >> r >> d >> u;
        l--;
        d--;
        imos.operation(l, d, r, u, 1);
    }
    auto a = imos.build();
    Ruisekiwa2D<AdditiveGroup<int>> sum(MAX, MAX);
    int base = 0;
    for (int i = 0 ; i < MAX ; i++)
        for (int j = 0 ; j < MAX ; j++) {
            if (a[i][j] == 0)
                base++;
            else if (a[i][j] == 1)
                sum.operation(i, j, 1);
        }
    auto solver = sum.build();
    for (auto [l, r, d, u] : A) {
        int ans = base + solver.product(l, d, r, u);
        cout << ans << '\n';
    }
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc434_d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
// #define PROBLEM "https://atcoder.jp/contests/abc434/tasks/abc434_d"

/*
 * AtCoder Beginner Contest 434 D - Clouds
 * https://atcoder.jp/contests/abc434/submissions/71932493
 */

#line 2 "Src/DataStructure/PrefixSum/PrefixSum2D.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 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/PrefixSum2D.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

namespace internal {

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

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

    explicit StaticRectSumSolver(const std::vector<std::vector<T>>& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_sum(m_H + 1, std::vector<T>(m_W + 1, G::identity())) {
        for (usize i = 0 ; i < m_H ; i++)
            for (usize j = 0 ; j < m_W ; j++)
                m_sum[i + 1][j + 1] = G::operation(
                        G::operation(m_sum[i + 1][j], m_sum[i][j + 1]), 
                        G::operation(G::inverse(m_sum[i][j]), a[i][j])
                        );
    }

    explicit StaticRectSumSolver(std::vector<std::vector<T>>&& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_sum{std::move(a)} {
        for (usize i = 0 ; i < m_H ; i++)
            m_sum[i].push_back(G::identity());
        m_sum.push_back(std::vector<T>(m_W + 1, G::identity()));
        for (usize i = 0 ; i <= m_H ; i++)
            for (usize j = m_W ; j-- ; )
                m_sum[i][j] = G::operation(m_sum[i][j], m_sum[i][j + 1]);
        for (usize i = m_H ; i-- ; )
            for (usize j = 0 ; j <= m_W ; j++)
                m_sum[i][j] = G::operation(m_sum[i][j], m_sum[i + 1][j]);
    }

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    // [l, r) x [d, u)
    T product(usize l, usize d, usize r, usize u) const {
        assert((l <= r and r <= height()) and "invalid i range: StaticRectSumSolver::product");
        assert((d <= u and u <= width()) and "invalid j range: StaticRectSumSolver::product");
        return G::operation(
                G::operation(m_sum[r][u], m_sum[l][d]),
                G::inverse(G::operation(m_sum[r][d], m_sum[l][u]))
                );
    }

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

    const_iterator begin() const {
        return m_sum.begin();
    }
    
    const_iterator end() const {
        return m_sum.end();
    }

private:

    usize m_H, m_W;

    std::vector<std::vector<T>> m_sum;
};

} // namespace internal

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

    Ruisekiwa2D(usize H, usize W) : m_H{H}, m_W{W}, m_a(H, std::vector<T>(W, G::identity())) {}

    explicit Ruisekiwa2D(std::vector<std::vector<T>>&& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_a{std::move(a)} {}

    explicit Ruisekiwa2D(const std::vector<std::vector<T>>& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_a{a} {}

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    void operation(usize i, usize j, T v) {
        assert((i < height() and j < width()) and "invalid range: Ruisekiwa2D::operation");
        assert(m_moved == false and "already destructed: Ruisekiwa2D::operation");
        m_a[i][j] = G::operation(m_a[i][j], v);
    }

    const std::vector<T>& operator[](const usize i) const {
        assert(i < height() and "invalid range: Ruisekiwa2D::operator[]");
        assert(m_moved == false and "already destructed: Ruisekiwa2D::operator[]");
        return m_a[i];
    }

    internal::StaticRectSumSolver<G> build() const {
        assert(m_moved == false and "already destructed: Ruisekiwa2D::build");
        return internal::StaticRectSumSolver<G>{m_a};
    }

    internal::StaticRectSumSolver<G> inplaceBuild() {
        assert(m_moved == false and "already destructed: Ruisekiwa2D::build");
        m_moved = true;
        return internal::StaticRectSumSolver<G>{std::move(m_a)};
    }

private:

    usize m_H = 0, m_W = 0;

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

    bool m_moved = false;
};

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

#line 5 "Src/DataStructure/PrefixSum/Imos2D.hpp"

#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 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 12 "Test/AtCoder/abc434_d.test.cpp"

#include <iostream>
#line 15 "Test/AtCoder/abc434_d.test.cpp"
#include <tuple>
using namespace std;
using namespace zawa;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
#ifdef ATCODER
    const int MAX = 2000;
    int N;
    cin >> N;
    Imos2D<AdditiveGroup<int>> imos(MAX, MAX);
    vector<tuple<int, int, int, int>> A(N);
    for (auto& [l, r, d, u] : A) {
        cin >> l >> r >> d >> u;
        l--;
        d--;
        imos.operation(l, d, r, u, 1);
    }
    auto a = imos.build();
    Ruisekiwa2D<AdditiveGroup<int>> sum(MAX, MAX);
    int base = 0;
    for (int i = 0 ; i < MAX ; i++)
        for (int j = 0 ; j < MAX ; j++) {
            if (a[i][j] == 0)
                base++;
            else if (a[i][j] == 1)
                sum.operation(i, j, 1);
        }
    auto solver = sum.build();
    for (auto [l, r, d, u] : A) {
        int ans = base + solver.product(l, d, r, u);
        cout << ans << '\n';
    }
#else
    cout << "Hello World\n";
#endif
}
Back to top page