Submission #1792992

---

Source Code Expand

#include <bits/stdc++.h>

#define int long long

using namespace std;

int a[2001][2001];
int d[3001][3001];
int f[3001][3001];
int r[3001][3001];
int dr[3001][3001];
int fr[3001][3001];

 main () {
	ios_base::sync_with_stdio (0);
	cin.tie (0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= m;j ++) {
			char te;
			cin >> te;
			if (te == '1') a[i][j] = 1;
			else a[i][j] = 0;
			if (a[i][j] && a[i][j - 1]) d[i][j] = 1;
			if (a[i][j] && a[i - 1][j]) f[i][j] = 1;
			r[i][j] = r[i - 1][j] + r[i][j - 1] - r[i - 1][j - 1] + a[i][j];
		}
	}
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= m;j ++) {
			dr[i][j] = dr[i - 1][j] + dr[i][j - 1] - dr[i - 1][j - 1] + d[i][j];
			fr[i][j] = fr[i - 1][j] + fr[i][j - 1] - fr[i - 1][j - 1] + f[i][j];	
		}
	} 
	while (q --) {
		int x, y, x1, y1;
		cin >> x >> y >> x1 >> y1;
		int cur = r[x1][y1] - r[x1][y - 1] - r[x - 1][y1] + r[x - 1][y - 1];
		int jkl = dr[x1][y1] - dr[x1][y] - dr[x - 1][y1] + dr[x - 1][y];
		int lkj = fr[x1][y1] - fr[x1][y - 1] - fr[x][y1] + fr[x][y - 1];
		cout << cur - jkl - lkj << endl;
	}
	return 0;
}

Submission Info

Judge Result