test/cuml_sum_2d.test.cpp

View this file on GitHub
Last update: 2024-05-04 20:54:20+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

Depends on

algo/cuml_sum_2d.hpp

Code

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

#include <bits/stdc++.h>
#include "../algo/cuml_sum_2d.hpp"
using namespace std;

int main() {
    int h, w, q;
    cin >> h >> w >> q;
    vector<string> a(h);
    for (int i = 0; i < h; i++) cin >> a[i];
    CumlSum2D sj(h, w), si(h, w), so(h, w);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            sj.assign(i, j, a[i][j] == 'J');
            si.assign(i, j, a[i][j] == 'I');
            so.assign(i, j, a[i][j] == 'O');
        }
    }
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--;
        cout << sj.sum(a, b, c, d) << ' ' << so.sum(a, b, c, d) << ' ' << si.sum(a, b, c, d) << endl;
    }
}

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

#include <bits/stdc++.h>
#line 2 "algo/cuml_sum_2d.hpp"
using namespace std;

template<typename T = long long>
struct CumlSum2D {
    CumlSum2D(size_t h, size_t w) : _h(h), _w(w), _s(h + 1, vector<T>(w + 1)), _a(h, vector<T>(w)), ready(false) {}
    CumlSum2D(vector<vector<T>> a) : _h(a.size()), _w(a.empty() ? 0 : a[0].size()), _s(_h, vector<T>(_w)), _a(a), ready(false) {}
    void assign(unsigned int i, unsigned int j, T x) {
        if (_a[i][j] != x) ready = false;
        _a[i][j] = x;
    }

    // [row_low, row_high), [col_low, col_high)
    // O(hw * (calls after changes))
    T sum(unsigned int row_low, unsigned int col_low, unsigned int row_high, unsigned int col_high) {
        if (!ready) {
            for (int i = 0; i < _h; i++) {
                for (int j = 0; j < _w; j++) {
                    _s[i + 1][j + 1] = _a[i][j];
                }
            }
            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];
                }
            }
            ready = true;
        }
        return _s[row_high][col_high] + _s[row_low][col_low] - _s[row_high][col_low] - _s[row_low][col_high];
    }
    private:
    int _h, _w;
    vector<vector<T>> _s, _a;
    bool ready;
};
#line 5 "test/cuml_sum_2d.test.cpp"
using namespace std;

int main() {
    int h, w, q;
    cin >> h >> w >> q;
    vector<string> a(h);
    for (int i = 0; i < h; i++) cin >> a[i];
    CumlSum2D sj(h, w), si(h, w), so(h, w);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            sj.assign(i, j, a[i][j] == 'J');
            si.assign(i, j, a[i][j] == 'I');
            so.assign(i, j, a[i][j] == 'O');
        }
    }
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--;
        cout << sj.sum(a, b, c, d) << ' ' << so.sum(a, b, c, d) << ' ' << si.sum(a, b, c, d) << endl;
    }
}