Forest density

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

using ll=long long;
using vl=vector<ll>;
#define all(c) begin(c),end(c)
#define pb push_back
#define sz(c) ll((c).size())

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)

#define TR(x) ({ if(1) cout << __LINE__ << ": " #x " = " << (x) << endl; })

// Only when needed
using dd = double;
const dd eps = 1e-10;
using vd = vector<dd>;
using vvd = vector<vd>;
using vvl = vector<vl>;

void solve(){
	ll n, q; cin >> n >> q;
	vvl pref(n + 1, vl(n + 1));
	FOR(i, 0, n){
		string s; cin >> s;
		vl row_pref(n + 1);
		FOR(i, 0, n) row_pref[i + 1] = row_pref[i] + (s[i] == '*');
		FOR(c, 0, n + 1) pref[i + 1][c] = pref[i][c] + row_pref[c];
	}
	FOR(i, 0, q){
		ll y1, x1, y2, x2;
		cin >> y1 >> x1 >> y2 >> x2;
		y1--, x1--;
		ll res = pref[y2][x2] + pref[y1][x1] - pref[y2][x1] - pref[y1][x2];
		cout << res << "\n";
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	solve();
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED