tests/cumsum2d.test.cpp

• View this file on GitHub
• Last update: 2025-01-22 03:51:11+00:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/0560

Depends on

• 2D cumulative sum (tools/cumsum2d.hpp)
• Typical groups (tools/group.hpp)
• Check whether T is a group (tools/is_group.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/cumsum2d.hpp"

using ll = long long;

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

  ll 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));

  std::vector<std::vector<ll>> J(M, std::vector<ll>(N, 0));
  std::vector<std::vector<ll>> O(M, std::vector<ll>(N, 0));
  std::vector<std::vector<ll>> I(M, std::vector<ll>(N, 0));
  for (ll y = 0; y < M; ++y) {
    for (ll 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::cumsum2d<ll> J_cumsum(J);
  tools::cumsum2d<ll> O_cumsum(O);
  tools::cumsum2d<ll> I_cumsum(I);

  for (ll i = 0; i < K; ++i) {
    ll a, b, c, d;
    std::cin >> a >> b >> c >> d;
    --a;
    --b;
    std::cout << J_cumsum.query(a, c, b, d) << ' ' << O_cumsum.query(a, c, b, d) << ' ' << I_cumsum.query(a, c, b, d) << '\n';
  }

  return 0;
}

#line 1 "tests/cumsum2d.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/cumsum2d.hpp"



#include <type_traits>
#include <cstddef>
#line 9 "tools/cumsum2d.hpp"
#include <cassert>
#line 1 "tools/is_group.hpp"



#line 5 "tools/is_group.hpp"
#include <utility>

namespace tools {

  template <typename G, typename = void>
  struct is_group : ::std::false_type {};

  template <typename G>
  struct is_group<G, ::std::enable_if_t<
    ::std::is_same_v<typename G::T, decltype(G::op(::std::declval<typename G::T>(), ::std::declval<typename G::T>()))> &&
    ::std::is_same_v<typename G::T, decltype(G::e())> &&
    ::std::is_same_v<typename G::T, decltype(G::inv(::std::declval<typename G::T>()))>
  , void>> : ::std::true_type {};

  template <typename G>
  inline constexpr bool is_group_v = ::tools::is_group<G>::value;
}


#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 12 "tools/cumsum2d.hpp"

namespace tools {

  template <typename X>
  class cumsum2d {
  private:
    using G = ::std::conditional_t<::tools::is_group_v<X>, X, tools::group::plus<X>>;
    using T = typename G::T;
    ::std::size_t height;
    ::std::size_t width;
    ::std::vector<T> preprocessed;

  public:
    template <typename Range>
    explicit cumsum2d(const Range& range) {
      const auto begin = ::std::begin(range);
      const auto end = ::std::end(range);
      this->height = ::std::distance(begin, end);
      this->width = this->height == 0 ? 0 : ::std::distance(::std::begin(*begin), ::std::end(*begin));
      this->preprocessed.reserve((this->height + 1) * (this->width + 1));
      ::std::fill_n(::std::back_inserter(this->preprocessed), (this->height + 1) * (this->width + 1), G::e());

      {
        auto it1 = begin;
        for (::std::size_t y = 0; y < this->height; ++y, ++it1) {
          auto it2 = ::std::begin(*it1);
          for (::std::size_t x = 0; x < this->width; ++x, ++it2) {
            this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)] = G::op(this->preprocessed[(y + 1) * (this->width + 1) + x], *it2);
          }
        }
      }
      for (::std::size_t x = 0; x < this->width; ++x) {
        for (::std::size_t y = 0; y < this->height; ++y) {
          this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)] = G::op(this->preprocessed[y * (this->width + 1) + (x + 1)], this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)]);
        }
      }
    }

    T query(const ::std::size_t y1, const ::std::size_t y2, const ::std::size_t x1, const ::std::size_t x2) const {
      assert(y1 <= y2 && y2 <= this->height);
      assert(x1 <= x2 && x2 <= this->width);
      return G::op(
        G::op(
          G::op(
            this->preprocessed[y2 * (this->width + 1) + x2],
            G::inv(this->preprocessed[y2 * (this->width + 1) + x1])
          ),
          G::inv(this->preprocessed[y1 * (this->width + 1) + x2])
        ),
        this->preprocessed[y1 * (this->width + 1) + x1]
      );
    }
  };
}


#line 9 "tests/cumsum2d.test.cpp"

using ll = long long;

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

  ll 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));

  std::vector<std::vector<ll>> J(M, std::vector<ll>(N, 0));
  std::vector<std::vector<ll>> O(M, std::vector<ll>(N, 0));
  std::vector<std::vector<ll>> I(M, std::vector<ll>(N, 0));
  for (ll y = 0; y < M; ++y) {
    for (ll 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::cumsum2d<ll> J_cumsum(J);
  tools::cumsum2d<ll> O_cumsum(O);
  tools::cumsum2d<ll> I_cumsum(I);

  for (ll i = 0; i < K; ++i) {
    ll a, b, c, d;
    std::cin >> a >> b >> c >> d;
    --a;
    --b;
    std::cout << J_cumsum.query(a, c, b, d) << ' ' << O_cumsum.query(a, c, b, d) << ' ' << I_cumsum.query(a, c, b, d) << '\n';
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	testcase_00	AC	5 ms	4 MB
g++	testcase_01	AC	5 ms	4 MB
g++	testcase_02	AC	6 ms	6 MB
g++	testcase_03	AC	23 ms	6 MB
g++	testcase_04	AC	27 ms	6 MB
g++	testcase_05	AC	61 ms	49 MB
g++	testcase_06	AC	64 ms	49 MB
g++	testcase_07	AC	69 ms	50 MB
g++	testcase_08	AC	69 ms	51 MB
g++	testcase_09	AC	66 ms	51 MB

Back to top page