Forest density

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <ll> vl;
typedef vector <vl> vvl;

void out (const vvl &a)
{
    for(auto x : a)
    {
        for(auto y : x)
            cerr << y << " ";
        cerr << "\n";
    }
    cerr << "\n";
}

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

    ll n, q, i, j, x1, y1, x2, y2;
    cin >> n >> q;
    vector <string> vs(n);
    for(i = 0; i < n; i++)
        cin >> vs[i];
    vvl f(n + 1, vl(n + 1, 0));
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            f[i + 1][j + 1] = f[i][j + 1] + f[i + 1][j] + (vs[i][j] == '*') - f[i][j];
    //out(f);
    while(q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << f[x2][y2] - f[x2][y1 - 1] - f[x1 - 1][y2] + f[x1 - 1][y1 - 1] << "\n";
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED