This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560"
#include <cstdio>
using namespace std;
#include "../../../algorithm/cumulative_sum_2d.cpp"
int main() {
int H, W, Q; scanf("%d%d%d", &H, &W, &Q);
vector< vector<int> > J(H, vector<int>(W)), O = J, I = J;
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
char c; scanf(" %c ", &c);
if(c == 'J') J[i][j]++;
if(c == 'O') O[i][j]++;
if(c == 'I') I[i][j]++;
}
}
auto add = [](int a, int b) { return a + b; };
auto sub = [](int a, int b) { return a - b; };
CumulativeSum2D<int> AJ(J, 0, add, sub);
CumulativeSum2D<int> AO(O, 0, add, sub);
CumulativeSum2D<int> AI(I, 0, add, sub);
while(Q--) {
int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
x1--, y1--;
int VJ = AJ.range_val(x1, y1, x2, y2);
int VO = AO.range_val(x1, y1, x2, y2);
int VI = AI.range_val(x1, y1, x2, y2);
printf("%d %d %d\n", VJ, VO, VI);
}
return 0;
}
#line 1 "verifying_test/AOJ/0560/cumulative_sum_2d.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560"
#include <cstdio>
using namespace std;
#line 2 "algorithm/cumulative_sum_2d.cpp"
/**
* @brief 2 次元累積和 (2 Dimension Cumulative Sum)
* @docs docs/algorithm/cumulative_sum_2d.md
*/
#include <functional>
#include <vector>
#include <cassert>
template <typename MonoidType>
struct CumulativeSum2D {
// 持つ矩形領域のサイズ
// 縦横とも、acc はこれより 2 大きくしておく
int n, m;
MonoidType E;
vector< vector<MonoidType> > acc;
using MMtoM = function< MonoidType(MonoidType, MonoidType) >;
MMtoM op, rop;
void accumulate() {
for(int i=0; i<=n; i++) {
for(int j=0; j<m; j++) {
acc[i][j+1] = op(acc[i][j+1], acc[i][j]);
}
}
for(int j=0; j<=m; j++) {
for(int i=0; i<n; i++) {
acc[i+1][j] = op(acc[i+1][j], acc[i][j]);
}
}
}
CumulativeSum2D() {}
CumulativeSum2D(int n_, int m_, int E_, MMtoM op_, MMtoM rop_) :
n(n_), m(m_), E(E_), acc(n_+2, vector<MonoidType>(m_+2, E_)),
op(op_), rop(rop_) {}
CumulativeSum2D(vector< vector<MonoidType> > mat, int E_,
MMtoM op_, MMtoM rop_,
bool need_accumulate = true) :
E(E_), op(op_), rop(rop_) {
assert(mat.size() > 0);
n = mat.size(), m = mat[0].size();
acc = vector< vector<MonoidType> >(n+2, vector<MonoidType>(m+2, E_));
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
acc[i+1][j+1] = mat[i][j];
}
}
if(need_accumulate) accumulate();
}
// [lx, rx), [ly, ry) の矩形領域に val を適用
void range_apply(int lx, int ly, int rx, int ry, MonoidType val) {
if(lx < 0 or ly < 0 or rx > n or ry > m) return;
lx++, ly++; rx++; ry++;
acc[lx][ly] = op(acc[lx][ly], val);
acc[rx][ry] = op(acc[rx][ry], val);
acc[lx][ry] = rop(acc[lx][ry], val);
acc[rx][ly] = rop(acc[rx][ly], val);
}
// [lx, rx), [ly, ry) の矩形領域の値
MonoidType range_val(int lx, int ly, int rx, int ry) {
if(lx < 0 or ly < 0 or rx > n or ry > m) return E;
MonoidType res = E;
res = op(res, acc[lx][ly]);
res = op(res, acc[rx][ry]);
res = rop(res, acc[lx][ry]);
res = rop(res, acc[rx][ly]);
return res;
}
};
#line 5 "verifying_test/AOJ/0560/cumulative_sum_2d.test.cpp"
int main() {
int H, W, Q; scanf("%d%d%d", &H, &W, &Q);
vector< vector<int> > J(H, vector<int>(W)), O = J, I = J;
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
char c; scanf(" %c ", &c);
if(c == 'J') J[i][j]++;
if(c == 'O') O[i][j]++;
if(c == 'I') I[i][j]++;
}
}
auto add = [](int a, int b) { return a + b; };
auto sub = [](int a, int b) { return a - b; };
CumulativeSum2D<int> AJ(J, 0, add, sub);
CumulativeSum2D<int> AO(O, 0, add, sub);
CumulativeSum2D<int> AI(I, 0, add, sub);
while(Q--) {
int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
x1--, y1--;
int VJ = AJ.range_val(x1, y1, x2, y2);
int VO = AO.range_val(x1, y1, x2, y2);
int VI = AI.range_val(x1, y1, x2, y2);
printf("%d %d %d\n", VJ, VO, VI);
}
return 0;
}