tests/disjoint_sparse_table_2d.test.cpp

• View this file on GitHub
• Last update: 2025-02-10 20:05:30+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/0560

Depends on

• Bit width required to represent a given integer (tools/bit_width.hpp)
• $\left\lceil \log_2(x) \right\rceil$ (tools/ceil_log2.hpp)
• 2D disjoint sparse table (tools/disjoint_sparse_table_2d.hpp)
• $\left\lfloor \log_2(x) \right\rfloor$ (tools/floor_log2.hpp)
• Typical groups (tools/group.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
• std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)
• $2^x$ (tools/pow2.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/0560

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include "tools/disjoint_sparse_table_2d.hpp"
#include "tools/group.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int M, N, K;
  std::cin >> M >> N >> K;
  std::vector<std::string> map;
  map.reserve(M);
  std::copy_n(std::istream_iterator<std::string>(std::cin), M, std::back_inserter(map));

  auto J = std::vector(M, std::vector<int>(N, 0));
  auto O = std::vector(M, std::vector<int>(N, 0));
  auto I = std::vector(M, std::vector<int>(N, 0));
  for (int y = 0; y < M; ++y) {
    for (int x = 0; x < N; ++x) {
      switch (map[y][x]) {
      case 'J':
        ++J[y][x];
        break;
      case 'O':
        ++O[y][x];
        break;
      case 'I':
        ++I[y][x];
        break;
      }
    }
  }

  tools::disjoint_sparse_table_2d<tools::group::plus<int>> J_dst(J);
  tools::disjoint_sparse_table_2d<tools::group::plus<int>> O_dst(O);
  tools::disjoint_sparse_table_2d<tools::group::plus<int>> I_dst(I);

  for (int i = 0; i < K; ++i) {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    --a;
    --b;
    std::cout << J_dst.prod(a, c, b, d) << ' ' << O_dst.prod(a, c, b, d) << ' ' << I_dst.prod(a, c, b, d) << '\n';
  }

  return 0;
}

#line 1 "tests/disjoint_sparse_table_2d.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/0560

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#line 1 "tools/disjoint_sparse_table_2d.hpp"



#line 5 "tools/disjoint_sparse_table_2d.hpp"
#include <cstddef>
#line 8 "tools/disjoint_sparse_table_2d.hpp"
#include <cassert>
#line 1 "tools/ceil_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 6 "tools/bit_width.hpp"
#include <type_traits>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x - 1);
  }
}


#line 1 "tools/pow2.hpp"



#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 1 "tools/floor_log2.hpp"



#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x) - 1;
  }
}


#line 12 "tools/disjoint_sparse_table_2d.hpp"

namespace tools {
  template <typename M>
  class disjoint_sparse_table_2d {
  private:
    using T = typename M::T;
    ::std::vector<::std::vector<T>> m_value;
    ::std::size_t m_height;
    ::std::size_t m_width;
    ::std::size_t m_hcapacity;
    ::std::size_t m_wcapacity;

  public:
    disjoint_sparse_table_2d() = default;
    disjoint_sparse_table_2d(const ::tools::disjoint_sparse_table_2d<M>&) = default;
    disjoint_sparse_table_2d(::tools::disjoint_sparse_table_2d<M>&&) = default;
    ~disjoint_sparse_table_2d() = default;
    ::tools::disjoint_sparse_table_2d<M>& operator=(const ::tools::disjoint_sparse_table_2d<M>&) = default;
    ::tools::disjoint_sparse_table_2d<M>& operator=(::tools::disjoint_sparse_table_2d<M>&&) = default;

    template <typename Range>
    explicit disjoint_sparse_table_2d(const Range& range) {
      const auto begin = ::std::begin(range);
      const auto end = ::std::end(range);
      this->m_height = ::std::distance(begin, end);
      this->m_width = this->m_height == 0 ? 0 : ::std::distance(::std::begin(*begin), ::std::end(*begin));
      assert(::std::all_of(begin, end, [&](const auto& row) { return static_cast<::std::size_t>(::std::distance(::std::begin(row), ::std::end(row))) == this->m_width; }));

      const auto hdepth = this->m_height <= 1 ? this->m_height : ::tools::ceil_log2(this->m_height);
      const auto wdepth = this->m_width <= 1 ? this->m_width : ::tools::ceil_log2(this->m_width);
      this->m_hcapacity = this->m_height <= 1 ? this->m_height : ::tools::pow2(hdepth);
      this->m_wcapacity = this->m_width <= 1 ? this->m_width : ::tools::pow2(wdepth);

      const auto construct_horizontal_dst = [&](::std::vector<T>& row) {
        row.resize(wdepth * this->m_wcapacity);
        ::std::fill(row.begin() + this->m_width, row.begin() + this->m_wcapacity, M::e());

        for (::std::size_t d = 1; d < wdepth; ++d) {
          const ::std::size_t offset = d * this->m_wcapacity;
          for (::std::size_t m = ::tools::pow2(d); m < this->m_wcapacity; m += ::tools::pow2(d + 1)) {
            row[offset + (m - 1)] = row[m - 1];
            row[offset + m] = row[m];
            for (::std::size_t l = m - 1; l --> m - ::tools::pow2(d);) {
              row[offset + l] = M::op(row[l], row[offset + (l + 1)]);
            }
            for (::std::size_t r = m + 2; r <= m + ::tools::pow2(d); ++r) {
              row[offset + (r - 1)] = M::op(row[offset + (r - 2)], row[r - 1]);
            }
          }
        }
      };

      this->m_value.resize(hdepth * this->m_hcapacity);
      for (auto& row : this->m_value) {
        row.reserve(wdepth * this->m_wcapacity);
      }
      for (::std::size_t h = 0; h < this->m_height; ++h) {
        ::std::copy(::std::begin(begin[h]), ::std::end(begin[h]), ::std::back_inserter(this->m_value[h]));
        construct_horizontal_dst(this->m_value[h]);
      }
      for (::std::size_t h = this->m_height; h < this->m_hcapacity; ++h) {
        this->m_value[h].resize(wdepth * this->m_wcapacity, M::e());
      }

      for (::std::size_t d = 1; d < hdepth; ++d) {
        const ::std::size_t offset = d * this->m_hcapacity;
        for (::std::size_t m = ::tools::pow2(d); m < this->m_hcapacity; m += ::tools::pow2(d + 1)) {
          ::std::copy(this->m_value[m - 1].begin(), this->m_value[m - 1].end(), ::std::back_inserter(this->m_value[offset + (m - 1)]));
          ::std::copy(this->m_value[m].begin(), this->m_value[m].end(), ::std::back_inserter(this->m_value[offset + m]));
          for (::std::size_t l = m - 1; l --> m - ::tools::pow2(d);) {
            for (::std::size_t w = 0; w < wdepth * this->m_wcapacity; ++w) {
              this->m_value[offset + l].push_back(M::op(this->m_value[l][w], this->m_value[offset + (l + 1)][w]));
            }
          }
          for (::std::size_t r = m + 2; r <= m + ::tools::pow2(d); ++r) {
            for (::std::size_t w = 0; w < wdepth * this->m_wcapacity; ++w) {
              this->m_value[offset + (r - 1)].push_back(M::op(this->m_value[offset + (r - 2)][w], this->m_value[r - 1][w]));
            }
          }
        }
      }
    }

    ::std::size_t height() const {
      return this->m_height;
    }
    ::std::size_t width() const {
      return this->m_width;
    }

    T prod(const ::std::size_t d, const ::std::size_t u, const ::std::size_t l, const ::std::size_t r) const {
      assert(d <= u && u <= this->m_height);
      assert(l <= r && r <= this->m_width);
      if (u - d == 0 || r - l == 0) {
        return M::e();
      } else if (u - d == 1 && r - l == 1) {
        return this->m_value[d][l];
      } else if (u - d == 1) {
        const ::std::size_t woffset = ::tools::floor_log2(l ^ (r - 1)) * this->m_wcapacity;
        return M::op(this->m_value[d][woffset + l], this->m_value[d][woffset + (r - 1)]);
      } else if (r - l == 1) {
        const ::std::size_t hoffset = ::tools::floor_log2(d ^ (u - 1)) * this->m_hcapacity;
        return M::op(this->m_value[hoffset + d][l], this->m_value[hoffset + (u - 1)][l]);
      } else {
        const ::std::size_t hoffset = ::tools::floor_log2(d ^ (u - 1)) * this->m_hcapacity;
        const ::std::size_t woffset = ::tools::floor_log2(l ^ (r - 1)) * this->m_wcapacity;
        return M::op(
          M::op(this->m_value[hoffset + d][woffset + l], this->m_value[hoffset + d][woffset + (r - 1)]),
          M::op(this->m_value[hoffset + (u - 1)][woffset + l], this->m_value[hoffset + (u - 1)][woffset + (r - 1)])
        );
      }
    }
  };
}


#line 1 "tools/group.hpp"



namespace tools {
  namespace group {
    template <typename G>
    struct plus {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs + rhs;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& v) {
        return -v;
      }
    };

    template <typename G>
    struct multiplies {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
      static T inv(const T& v) {
        return e() / v;
      }
    };

    template <typename G>
    struct bit_xor {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs ^ rhs;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& v) {
        return v;
      }
    };
  }
}


#line 10 "tests/disjoint_sparse_table_2d.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int M, N, K;
  std::cin >> M >> N >> K;
  std::vector<std::string> map;
  map.reserve(M);
  std::copy_n(std::istream_iterator<std::string>(std::cin), M, std::back_inserter(map));

  auto J = std::vector(M, std::vector<int>(N, 0));
  auto O = std::vector(M, std::vector<int>(N, 0));
  auto I = std::vector(M, std::vector<int>(N, 0));
  for (int y = 0; y < M; ++y) {
    for (int x = 0; x < N; ++x) {
      switch (map[y][x]) {
      case 'J':
        ++J[y][x];
        break;
      case 'O':
        ++O[y][x];
        break;
      case 'I':
        ++I[y][x];
        break;
      }
    }
  }

  tools::disjoint_sparse_table_2d<tools::group::plus<int>> J_dst(J);
  tools::disjoint_sparse_table_2d<tools::group::plus<int>> O_dst(O);
  tools::disjoint_sparse_table_2d<tools::group::plus<int>> I_dst(I);

  for (int i = 0; i < K; ++i) {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    --a;
    --b;
    std::cout << J_dst.prod(a, c, b, d) << ' ' << O_dst.prod(a, c, b, d) << ' ' << I_dst.prod(a, c, b, d) << '\n';
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	testcase_00	AC	6 ms	4 MB
g++	testcase_01	AC	10 ms	8 MB
g++	testcase_02	AC	49 ms	50 MB
g++	testcase_03	AC	72 ms	50 MB
g++	testcase_04	AC	74 ms	50 MB
g++	testcase_05	AC	1273 ms	1245 MB
g++	testcase_06	AC	1175 ms	1246 MB
g++	testcase_07	AC	1093 ms	1246 MB
g++	testcase_08	AC	1098 ms	1246 MB
g++	testcase_09	AC	1090 ms	1246 MB

Back to top page