Forest density

buffer = input().split()
n = int(buffer[0])
q = int(buffer[1])
forest = []
for _ in range(n):
    forest.append(input())
queries = []
for _ in range(q):
    queries.append(list(map(int,input().split())))

rectangles = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,n+1):
    line_count = 0
    for j in range(1,n+1):
        if forest[i-1][j-1] == '*':
            line_count += 1
        rectangles[i][j] += line_count
        if i > 0:
            rectangles[i][j] += rectangles[i-1][j]

for query in queries:
    res = rectangles[query[2]][query[3]]
    res += rectangles[query[0]-1][query[1]-1]
    res -= rectangles[query[0]-1][query[3]]
    res -= rectangles[query[2]][query[1]-1]
    print(res)
#print(rectangles)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED