Forest density

#include <bits/stdc++.h>

using namespace std;

int main() {

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

    int **forest = new int*[n];
    for (int i = 0; i < n; i++)
        forest[i] = new int[n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char c;
            cin >> c;
            forest[i][j] = (c == '*') ? 1 : 0;
        }
    }
    
    long long **prefix = new long long*[n];
    for (int i = 0; i < n; i++)
        prefix[i] = new long long[n];
    
    prefix[0][0] = forest[0][0];
    for (int j = 1; j < n; j++)
        prefix[0][j] = prefix[0][j-1] + forest[0][j];
    
    for (int i = 1; i < n; i++) {

        long long count_on_line = forest[i][0];
        prefix[i][0] = prefix[i-1][0] + forest[i][0];

        for (int j = 1; j < n; j++) {
            count_on_line += forest[i][j];
            prefix[i][j] = prefix[i-1][j] + count_on_line;
        }
    }

    long long *output = new long long[q];

    for (int i = 0; i < q; i++) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--, x1--, y2--, x2--;

        long long a = prefix[y2][x2];
        long long b = (y1 > 0) ? prefix[y1-1][x2] : 0;
        long long c = (x1 > 0) ? prefix[y2][x1-1] : 0;
        long long d = (x1 > 0 && y1 > 0) ? prefix[y1-1][x1-1] : 0;

        output[i] = a - b - c + d;
    }

    for (int i = 0; i < q; i++)
        cout << output[i] << endl;

    return 0;

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED