Forest density

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

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

    int n, q;
    cin >> n >> q;

    vector<vector<int>> S(n + 1, vector<int>(n + 1, 0));

    for(int i = 1; i <= n; ++i){
        string row;
        cin >> row;
        for(int j = 1; j <= n; ++j){
            int tree = (row[j-1] == '*') ? 1 : 0;
            S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + tree;
        }
    }

    string output = "";
    for(int q_num = 0; q_num < q; ++q_num){
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        int count = S[y2][x2] - S[y1 - 1][x2] - S[y2][x1 - 1] + S[y1 - 1][x1 - 1];
        output += to_string(count) + "\n";
    }

    cout << output;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED