Forest density

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

#define SEG_OP(a,b) a ^ b

const int N = 1001;

int S[N][N];

int n, q;

int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			char c;
			cin >> c;
			S[i][j] = c == '*';
		}
	}
	for (int i = 1; i <= n; ++i) {
		int s = 0;
		for (int j = 1; j <= n; ++j) {
			s += S[i][j];
			S[i][j] = s + S[i-1][j];
		}
	}
	for (int i = 0; i < q; ++i) {
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;
		if (x2 < x1) swap(x1,x2);
		if (y2 < y1) swap(y1,y2);
		--x1; --y1;
		cout << S[y1][x1] + S[y2][x2] - S[y2][x1] - S[y1][x2] << '\n';
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED