Forest density

// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
#include <climits>
 
using namespace std;
 
int main() {
    int n, q;
    cin >> n >> q;
    
    vector<vector<int>> trees(n+1, vector<int>(n+1, 0));
    
    for (int y = 0; y < n; y++)
    {
        string s;
        cin >> s;
        for (int x = 0; x < n; x++)
        {
            trees[y+1][x+1] = (s[x] == '*') + trees[y][x+1] + trees[y+1][x] - trees[y][x];
        }
    }
    
    for (int i = 0; i < q; i++)
    {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        
        int res = trees[y2][x2] - trees[y1-1][x2] - trees[y2][x1-1] + trees[y1-1][x1-1];
        cout << res << endl;
    }
    
    
 
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED