Forest density

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

#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)(x).size()                                 // signed size: avoids the unsigned .size() wrap bug

using ll  = long long;
using pii = pair<int,int>;
using vi  = vector<int>;

#ifdef LOCAL                                                    // compile with -DLOCAL to enable, silent on the judge
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", dbg_out(__VA_ARGS__)
template<class T> void dbg_out(T x) { cerr << x << '\n'; }
template<class T, class... R> void dbg_out(T x, R... r) { cerr << x << ", "; dbg_out(r...); }
#else
#define dbg(...)
#endif

int main() {
    cin.tie(0)->sync_with_stdio(0);                             // never mix with scanf/printf after this
    // int n; cin >> n; 
    int n,q; cin >> n >> q; 
    // vi a(n); for (auto &x : a) cin >> x;


    vector<vector<char>> grid(n, vector<char>(n));
    vector<vector<int>> cum(n+1, vector<int>(n+1, 0));


    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> grid[i][j];
            int cell = 0;
            if (grid[i][j] == '*')
            {
                cell = 1;
            }
            cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + cell;

            // cout << cum[i+1][j+1] << " \n"[j ==n-1];

        }
        
    }





    int a,b , c,d;
    while (cin >> a >> b >> c >> d)
    {
        int out = cum[c][d] - cum[a-1][d] - cum[c][b-1] + cum[a-1][b-1];
        cout << out << "\n";
    }
    
    


    // cout << ;
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED