test/aoj/0560.test.cpp

View this file on GitHub
Last update: 2023-01-03 23:55:29+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

Depends on

src/dp/cumulative_sum_2d.hpp

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "../../src/dp/cumulative_sum_2d.hpp"

int main() {
  int M, N, K;
  cin >> M >> N >> K;
  vector<vector<long long>> jgrid(M, vector<long long>(N, 0));
  vector<vector<long long>> ogrid(M, vector<long long>(N, 0));
  vector<vector<long long>> igrid(M, vector<long long>(N, 0));
  for (int i = 0; i < M; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < N; ++j) {
      if (s[j] == 'J') {
        jgrid[i][j] = 1;
      } else if (s[j] == 'O') {
        ogrid[i][j] = 1;
      } else {
        igrid[i][j] = 1;
      }
    }
  }
  CumulativeSum2d<long long> jcum(jgrid);
  CumulativeSum2d<long long> ocum(ogrid);
  CumulativeSum2d<long long> icum(igrid);
  for (int i = 0; i < K; ++i) {
    int y1, x1, y2, x2;
    cin >> y1 >> x1 >> y2 >> x2;
    --y1;
    --x1;
    cout << jcum.sum(x1, y1, x2, y2) << " " << ocum.sum(x1, y1, x2, y2) << " "
         << icum.sum(x1, y1, x2, y2) << endl;
  }
}

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

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/dp/cumulative_sum_2d.hpp"

#line 4 "src/dp/cumulative_sum_2d.hpp"
using namespace std;

template <typename T> struct CumulativeSum2d {
private:
  vector<vector<T>> s;

public:
  CumulativeSum2d(const vector<vector<T>> &grid) {
    int h = grid.size();
    int w = grid[0].size();
    s.resize(h + 1, vector<T>(w + 1, 0));
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + grid[i][j];
      }
    }
  }

  // [x1, x2) [y1, y2), x1 and x2, y1, y2 is 0-indexed.
  T sum(int x1, int y1, int x2, int y2) {
    return s[y2][x2] - s[y1][x2] - s[y2][x1] + s[y1][x1];
  }
};
#line 7 "test/aoj/0560.test.cpp"

int main() {
  int M, N, K;
  cin >> M >> N >> K;
  vector<vector<long long>> jgrid(M, vector<long long>(N, 0));
  vector<vector<long long>> ogrid(M, vector<long long>(N, 0));
  vector<vector<long long>> igrid(M, vector<long long>(N, 0));
  for (int i = 0; i < M; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < N; ++j) {
      if (s[j] == 'J') {
        jgrid[i][j] = 1;
      } else if (s[j] == 'O') {
        ogrid[i][j] = 1;
      } else {
        igrid[i][j] = 1;
      }
    }
  }
  CumulativeSum2d<long long> jcum(jgrid);
  CumulativeSum2d<long long> ocum(ogrid);
  CumulativeSum2d<long long> icum(igrid);
  for (int i = 0; i < K; ++i) {
    int y1, x1, y2, x2;
    cin >> y1 >> x1 >> y2 >> x2;
    --y1;
    --x1;
    cout << jcum.sum(x1, y1, x2, y2) << " " << ocum.sum(x1, y1, x2, y2) << " "
         << icum.sum(x1, y1, x2, y2) << endl;
  }
}