Forest density

import sys
input = sys.stdin.read

def solve():
    # Read all input at once
    data = input().split()
    
    # Parse first line
    n = int(data[0])
    q = int(data[1])
    
    # Initialize prefix sum array (n+1 by n+1 for easier calculation)
    prefix = [[0] * (n + 1) for _ in range(n + 1)]
    
    # Build the prefix sum array from the grid
    idx = 2  # Start reading the grid from the 2nd element in `data`
    for i in range(1, n + 1):
        row = data[idx]
        for j in range(1, n + 1):
            prefix[i][j] = (1 if row[j-1] == '*' else 0) \
                           + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
        idx += 1  # Move to the next row in the input
    
    # Prepare output list for results
    output = []
    
    # Process each query
    for k in range(q):
        y1 = int(data[idx])
        x1 = int(data[idx+1])
        y2 = int(data[idx+2])
        x2 = int(data[idx+3])
        result = prefix[y2][x2] - prefix[y1-1][x2] - prefix[y2][x1-1] + prefix[y1-1][x1-1]
        output.append(str(result))
        idx += 4  # Move to the next query
    
    # 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