This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Harui-i/library
#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; } }