test/verify/aoj-0560.test.cpp

View this file on GitHub
Last update: 2024-08-21 21:41:37+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560"

#include "template/template.hpp"
#include "dp/cumulative-sum-2d.hpp"

int main () {
  int M, N; cin >> M >> N;
  int K; cin >> K;
  CumulativeSum2D<int>J(M,N);
  CumulativeSum2D<int>O(M,N);
  CumulativeSum2D<int>I(M,N);
  for(int i=0; i<M; i++) {
    string S; cin >> S;
    assert(S.size() == N);
    for(int j=0; j<S.size(); j++) {
      if (S[j] == 'J') J.add(i,j,1);
      if (S[j] == 'O') O.add(i,j,1);
      if (S[j] == 'I') I.add(i,j,1);
    }
  }

  J.build(); O.build(); I.build(); 

  for(int i=0; i<K; i++) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    a--; b--;
    cout << J.query(a,b,c,d) << " " << O.query(a,b,c,d) << " " << I.query(a,b,c,d) << endl;
  }
}

#line 1 "test/verify/aoj-0560.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560"

#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 1 "dp/cumulative-sum-2d.hpp"



#line 5 "dp/cumulative-sum-2d.hpp"
#include <vector>

template<class T>
struct CumulativeSum2D {
  bool has_built = false;
  int H, W;
  std::vector<std::vector<T>> data;

  CumulativeSum2D(int _H, int _W)  : H(_H), W(_W), data(std::vector<std::vector<T>>(H+1, std::vector<T>(W+1))) {
  }

  void add (int i, int j, T x) {
    assert(0 <= i && i < H && 0 <= j && j < W && !has_built);
    data[i+1][j+1] += x;
  }

  // https://ngtkana.hatenablog.com/entry/2023/12/04/194327
  // 1B
  void build() {
    assert(!has_built);
    for (int i=1; i<=H; i++) {
      for (int j=1; j<=W; j++) {
        data[i][j] += data[i-1][j];
      }
    }

    for (int i=1; i<=H; i++) {
      for (int j=1; j<=W; j++) {
        data[i][j] += data[i][j-1];
      }
    }


    has_built = true;
  }

  // [si, gi) * [sj, gj)
  T query(int si, int sj, int gi, int gj) {
    assert(has_built);
    assert(0 <= si && si < H && 0 <= sj && sj < W);
    assert(0 <= gi && gi <= H && 0 <= gj && gj <= W);
    assert(si <= gi && sj <= gj);
    return data[gi][gj] - data[si][gj] - data[gi][sj] + data[si][sj];
  }
};

#line 5 "test/verify/aoj-0560.test.cpp"

int main () {
  int M, N; cin >> M >> N;
  int K; cin >> K;
  CumulativeSum2D<int>J(M,N);
  CumulativeSum2D<int>O(M,N);
  CumulativeSum2D<int>I(M,N);
  for(int i=0; i<M; i++) {
    string S; cin >> S;
    assert(S.size() == N);
    for(int j=0; j<S.size(); j++) {
      if (S[j] == 'J') J.add(i,j,1);
      if (S[j] == 'O') O.add(i,j,1);
      if (S[j] == 'I') I.add(i,j,1);
    }
  }

  J.build(); O.build(); I.build(); 

  for(int i=0; i<K; i++) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    a--; b--;
    cout << J.query(a,b,c,d) << " " << O.query(a,b,c,d) << " " << I.query(a,b,c,d) << endl;
  }
}