verify/Datastructure_static2dsum.test.cpp

View this file on GitHub
Last update: 2025-02-19 15:02:43+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560"
#include "../Utility/template.hpp"
#include "../Datastructure/static2dsum.hpp"

int main() {
    int h, w;
    cin >> h >> w;
    int k;
    cin >> k;
    static2dsum<ll> J(h, w);
    static2dsum<ll> O(h, w);
    static2dsum<ll> I(h, w);


    rep(i, 0, h) rep(j, 0, w) {
        char a;
        cin >> a;
        if(a=='J') J.add(i, j, 1);
        if(a=='O') O.add(i, j, 1);
        if(a=='I') I.add(i, j, 1);
    }

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


    while(k--) {
        int sy, sx, ty, tx;
        cin >> sy >> sx >> ty >> tx;
        sy--, sx--;
        cout << J.prod(sx, tx, sy, ty) << " ";
        cout << O.prod(sx, tx, sy, ty) << " ";
        cout << I.prod(sx, tx, sy, ty) << endl;

    }
	

}

#line 1 "verify/Datastructure_static2dsum.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/static2dsum.hpp"
TT struct static2dsum {
    int id(int i, int j) const {
        return i * (w + 1) + j;
    }
    int h, w;
    vector<T> d;
    bool built = false;

    static2dsum(int h = 0, int w = 0)
        : static2dsum(vector<vector<T>>(h, vector<T>(w, T()))) {
    }

    static2dsum(vec<vec<T>> const &dat) {
        h = dat.size();
        if (h)
            w = dat[0].size();
        else
            w = 0;
        d.resize((h + 1) * (w + 1), 0);
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                d[id(i + 1, j + 1)] = dat[i][j];
            }
        }
    }
    void add(int i, int j, T x) {
        assert(built == false);
        d[id(i + 1, j + 1)] += x;
    }

    void build() {
        assert(built == false);
        for (int i = 0; i <= h; ++i) {
            for (int j = 0; j < w; ++j) {
                d[id(i, j + 1)] += d[id(i, j)];
            }
        }

        for (int j = 0; j <= w; ++j) {
            for (int i = 0; i < h; ++i) {
                d[id(i + 1, j)] += d[id(i, j)];
            }
        }

        built = true;
    }

    T get(int y, int x) const {
        assert(built);
        assert(0 <= y && y < h);
        assert(0 <= x && x < w);
        return prod(x, x + 1, y, y + 1);
    }

    T prod(int sx, int tx, int sy, int ty) const {
        assert(built);
        assert(0 <= sy && sy <= ty && ty <= h);
        assert(0 <= sx && sx <= tx && tx <= w);

        T res = d[id(ty, tx)];
        res -= d[id(sy, tx)];
        res -= d[id(ty, sx)];
        res += d[id(sy, sx)];
        return res;
    }
};
#line 4 "verify/Datastructure_static2dsum.test.cpp"

int main() {
    int h, w;
    cin >> h >> w;
    int k;
    cin >> k;
    static2dsum<ll> J(h, w);
    static2dsum<ll> O(h, w);
    static2dsum<ll> I(h, w);


    rep(i, 0, h) rep(j, 0, w) {
        char a;
        cin >> a;
        if(a=='J') J.add(i, j, 1);
        if(a=='O') O.add(i, j, 1);
        if(a=='I') I.add(i, j, 1);
    }

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


    while(k--) {
        int sy, sx, ty, tx;
        cin >> sy >> sx >> ty >> tx;
        sy--, sx--;
        cout << J.prod(sx, tx, sy, ty) << " ";
        cout << O.prod(sx, tx, sy, ty) << " ";
        cout << I.prod(sx, tx, sy, ty) << endl;

    }
	

}