Submission #2232941

---

Source Code Expand

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

using ll = long long;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SIZE(a) ((int)(a).size())

const int N = 2005;

int n, m, q;
char s[N][N];

int s1[N][N], s2[N][N], s3[N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> q;
	REP(i, n) cin >> (s[i+1] + 1);

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (s[i][j] == '1') {
				++s1[i][j];
				if (j > 1 && s[i][j-1] == '1') ++s2[i][j];
				if (i > 1 && s[i-1][j] == '1') ++s3[i][j];
			}
			s1[i][j] += s1[i-1][j] + s1[i][j-1] - s1[i-1][j-1];
			s2[i][j] += s2[i-1][j] + s2[i][j-1] - s2[i-1][j-1];
			s3[i][j] += s3[i-1][j] + s3[i][j-1] - s3[i-1][j-1];
		}
	}

	REP(i, q) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		--x1; --y1;
		int x = s1[x2][y2] - s1[x1][y2] - s1[x2][y1] + s1[x1][y1];
		++y1;
		int y = s2[x2][y2] - s2[x1][y2] - s2[x2][y1] + s2[x1][y1];
		--y1; ++x1;
		int z = s3[x2][y2] - s3[x1][y2] - s3[x2][y1] + s3[x1][y1];
		int result = x-y-z;
		cout << result << '\n';
	}

	return 0;
}

Submission Info

Judge Result