Submission #1603837

---

Source Code Expand

// #include {{{
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iterator>
#include <tuple>
#include <utility>
#include <random>
#include <limits>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <cassert>
// }}}

using namespace std;

// macros {{{
template<typename T, size_t N>
constexpr size_t NELEMS(T (&)[N]) { return N; }

template<typename InputIt>
void PRINT_RANGE(InputIt first, InputIt last)
{
    for(; first != last; ++first)
        cout << *first << (first==last ? "" : " ");
    cout << "\n";
}

template<typename T>
void PRINT_MATRIX(T mat, size_t nr, size_t nc)
{
    for(size_t r = 0; r < nr; ++r) {
        for(size_t c = 0; c < nc; ++c) {
            cout << mat[r][c] << (c==nc-1 ? "" : " ");
        }
        cout << "\n";
    }
}

#define FOR(i, start, end) for(int i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)
// }}}

// types {{{
using ll  = long long;
using ull = unsigned long long;
// }}}

ll N, M, Q;
vector<vector<int>> S;

vector<vector<ll>> V;  // 頂点数
vector<vector<ll>> EH; // 水平な辺の数
vector<vector<ll>> EV; // 垂直な辺の数

void init()
{
    V.assign(N+1, vector<ll>(M+1, 0));

    FOR(y, 1, N+1) {
        FOR(x, 1, M+1) {
            V[y][x] = V[y-1][x] + V[y][x-1] - V[y-1][x-1] + S[y][x];
        }
    }

    EH.assign(N+1, vector<ll>(M+1, 0));
    EV.assign(N+1, vector<ll>(M+1, 0));
    FOR(y, 1, N+1) {
        FOR(x, 1, M+1) {
            EH[y][x] = EH[y-1][x] + EH[y][x-1] - EH[y-1][x-1];
            if(S[y][x] == 1 && S[y][x-1] == 1)
                ++EH[y][x];

            EV[y][x] = EV[y-1][x] + EV[y][x-1] - EV[y-1][x-1];
            if(S[y][x] == 1 && S[y-1][x] == 1)
                ++EV[y][x];
        }
    }

#if DEBUG
    PRINT_MATRIX(V,  N+1, M+1);
    PRINT_MATRIX(EH, N+1, M+1);
    PRINT_MATRIX(EV, N+1, M+1);
#endif
}

void solve()
{
    init();

    REP(_, Q) {
        int x1, y1;
        int x2, y2;
        cin >> y1 >> x1;
        cin >> y2 >> x2;

        ll v = V[y2][x2] - V[y2][x1-1] - V[y1-1][x2] + V[y1-1][x1-1];

        ll eh = EH[y2][x2] - EH[y2][x1] - EH[y1-1][x2] + EH[y1-1][x1];
        ll ev = EV[y2][x2] - EV[y2][x1-1] - EV[y1][x2] + EV[y1][x1-1];

        ll ans = v - eh - ev;
        cout << ans << "\n";
    }
}

int main()
{
    cin >> N >> M >> Q;
    S.assign(N+1, vector<int>(M+1, false));
    FOR(y, 1, N+1) {
        string s;
        cin >> s;
        transform(begin(s), end(s), begin(S[y])+1, [](char c) {
            return c == '1' ? 1 : 0;
        });
    }
    //PRINT_MATRIX(S, N+1, M+1);

    solve();

    return 0;
}

Submission Info

Judge Result