Forest density

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>

using namespace std;

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

    // freopen("input.txt", "r", stdin); // TODO: REMOVE THIS YOU STUPID ****

    int n, q;
    cin >> n >> q;
    vector<vector<long long>> values(n+1, vector<long long>(n+1, 0));
    for (int i = 1; i <= n; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < n; j++) {
            if (line[j] == '*') values[i][j+1] = 1;
        }
    }
    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= n; x++) {
            values[y][x] += values[y-1][x] + values[y][x-1] - values[y-1][x-1];
        }
    }

    for (int i = 0; i < q; i++) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        long long rb = values[y2][x2];
        long long l = values[y1-1][x2];
        long long t = values[y2][x1-1];
        long long lt = values[y1-1][x1-1];
        long long result = rb - l - t + lt;
        cout << result << endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED