Forest density

import sys
input = sys.stdin.read

def solve():
    # Read all input at once
    data = input().splitlines()
    
    # Parse first line
    n, q = map(int, data[0].split())
    
    # Initialize grid and prefix sum array
    grid = data[1:n+1]
    prefix = [[0] * (n + 1) for _ in range(n + 1)]
    
    # Build the prefix sum array
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            prefix[i][j] = (1 if grid[i-1][j-1] == '*' else 0) \
                           + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
    
    # Prepare output list for results
    output = []
    
    # Process each query
    for idx in range(n+1, n+1+q):
        y1, x1, y2, x2 = map(int, data[idx].split())
        result = prefix[y2][x2] - prefix[y1-1][x2] - prefix[y2][x1-1] + prefix[y1-1][x1-1]
        output.append(str(result))
    
    # Output all results at once
    sys.stdout.write("\n".join(output) + "\n")

# Example usage:
solve()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: ACCEPTED