Forest density

def process_forest_queries(n, q, forest, queries):
    prefix_sum = [[0] * (n + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            tree_count = 1 if forest[i-1][j-1] == '*' else 0
            prefix_sum[i][j] = (prefix_sum[i-1][j] 
                                + prefix_sum[i][j-1] 
                                - prefix_sum[i-1][j-1] 
                                + tree_count)

    results = []
    for y1, x1, y2, x2 in queries:
        total_trees = (prefix_sum[y2][x2]
                       - prefix_sum[y1-1][x2]
                       - prefix_sum[y2][x1-1]
                       + prefix_sum[y1-1][x1-1])
        results.append(total_trees)
    
    return results

n, q = map(int, input().split())
forest = [input().strip() for _ in range(n)]
queries = [tuple(map(int, input().split())) for _ in range(q)]

results = process_forest_queries(n, q, forest, queries)
print("\n".join(map(str, results)))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED