Forest density

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

typedef long long ll;


int main() {
    ll n,q;
    cin >> n;
    cin >> q;

    

    ll val[n+1][n+1] = {0};
    for(ll i = 0; i <= n; i++) {
        for(ll j = 0; j <= n; j++) {
            val[i][j] = 0;
        }
    }

    // for(ll i = 0; i < n; i++) {
    //     for(ll j = 0; j<n; j++) {
    //         cout << val[i+1][j+1] << " ";
    //     }
    //     cout << endl;
    // }
    
    for(ll i = 0; i < n; i++) {
        for(ll j = 0; j < n; j++) {
            char tmp;
            ll sum = 0;
            cin >> tmp;
            if(tmp == '*') sum += 1;
            sum += val[i][j+1];
            sum += val[i+1][j];
            sum -= val[i][j];

            val[i+1][j+1] = sum;
        }
    }

    // for(ll i = 0; i < n; i++) {
    //     for(ll j = 0; j<n; j++) {
    //         cout << val[i+1][j+1] << " ";
    //     }
    //     cout << endl;
    // }

    ll a,b,c,d;
    

    ll result[q];
    ll result_id = 0;
    
    for(ll q_id = 0; q_id < q; q_id++){
        cin >> a;
        cin >> b;
        cin >>c;
        cin>>d;

        

        result[result_id] = val[c][d] - val[a-1][d] - val[c][b-1] + val[a-1][b-1];
        result_id++;
    }

    for(ll i = 0; i < result_id; i++) {
        cout << result[i] << endl;
    }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED