Forest density

def solve():
    # Input reading
    n, q = map(int, input().split())
    grid = [input().strip() for _ in range(n)]
    
    # Initialize the prefix sum array with an extra row and column of zeros for easy calculations
    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):
            # Convert grid values to 1 if it's a tree ('*'), otherwise 0
            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]
    
    # Process each query
    for _ in range(q):
        y1, x1, y2, x2 = map(int, input().split())
        # Use the inclusion-exclusion principle to calculate the number of trees in the rectangle
        result = prefix[y2][x2] - prefix[y1-1][x2] - prefix[y2][x1-1] + prefix[y1-1][x1-1]
        print(result)

# Example usage:
solve()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED