Python(C++)でJOI難易度5を埋める #30

A - 惑星探査 (Planetary Exploration)

PythonだとTLE，PyPyだとMLEで死ぬので，C++で解く．許して．二次元累積和

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

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<string> geo(m);
    vector<vector<int>> query(k, vector<int>(4));
    for (int i = 0; i < m; i++) {
        cin >> geo.at(i);
    }
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> query.at(i).at(j);
        }
    }

    vector<vector<int>> cnt_j(m + 1, vector<int>(n + 1));
    vector<vector<int>> cnt_o(m + 1, vector<int>(n + 1));
    vector<vector<int>> cnt_i(m + 1, vector<int>(n + 1));

    int tmp_j, tmp_o, tmp_i;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0) {
                tmp_j = cnt_j.at(i + 1).at(j);
                tmp_o = cnt_o.at(i + 1).at(j);
                tmp_i = cnt_i.at(i + 1).at(j);
            }
            else if (j == 0) {
                tmp_j = cnt_j.at(i).at(j + 1);
                tmp_o = cnt_o.at(i).at(j + 1);
                tmp_i = cnt_i.at(i).at(j + 1);
            }
            else {
                tmp_j = cnt_j.at(i).at(j + 1) + cnt_j.at(i + 1).at(j) - cnt_j.at(i).at(j);
                tmp_o = cnt_o.at(i).at(j + 1) + cnt_o.at(i + 1).at(j) - cnt_o.at(i).at(j);
                tmp_i = cnt_i.at(i).at(j + 1) + cnt_i.at(i + 1).at(j) - cnt_i.at(i).at(j);
            }

            if (geo.at(i).at(j) == 'J') {
                cnt_j.at(i + 1).at(j + 1) = tmp_j + 1;
                cnt_o.at(i + 1).at(j + 1) = tmp_o;
                cnt_i.at(i + 1).at(j + 1) = tmp_i;
            }
            if (geo.at(i).at(j) == 'O') {
                cnt_j.at(i + 1).at(j + 1) = tmp_j;
                cnt_o.at(i + 1).at(j + 1) = tmp_o + 1;
                cnt_i.at(i + 1).at(j + 1) = tmp_i;
            }
            if (geo.at(i).at(j) == 'I') {
                cnt_j.at(i + 1).at(j + 1) = tmp_j;
                cnt_o.at(i + 1).at(j + 1) = tmp_o;
                cnt_i.at(i + 1).at(j + 1) = tmp_i + 1;
            }
        }
    }
    for (int i = 0; i < k; i++) {
        int q_s_y = query.at(i).at(0);
        int q_s_x = query.at(i).at(1);
        int q_e_y = query.at(i).at(2);
        int q_e_x = query.at(i).at(3);

        int ans_j = cnt_j.at(q_e_y).at(q_e_x) - cnt_j.at(q_e_y).at(q_s_x - 1) - cnt_j.at(q_s_y - 1).at(q_e_x) + cnt_j.at(q_s_y - 1).at(q_s_x - 1);
        int ans_o = cnt_o.at(q_e_y).at(q_e_x) - cnt_o.at(q_e_y).at(q_s_x - 1) - cnt_o.at(q_s_y - 1).at(q_e_x) + cnt_o.at(q_s_y - 1).at(q_s_x - 1);
        int ans_i = cnt_i.at(q_e_y).at(q_e_x) - cnt_i.at(q_e_y).at(q_s_x - 1) - cnt_i.at(q_s_y - 1).at(q_e_x) + cnt_i.at(q_s_y - 1).at(q_s_x - 1);

        cout << ans_j << ' ' <<  ans_o << ' ' << ans_i << endl;
    }
}

Python→TLE，PyPy→MLEしたので，C++で提出