Forest density

from time import time
import sys
input = sys.stdin.readline



def print2d(ma):
    for line in ma:
        for ch in line:
            print(ch, end=" ")
        print()

size, queryCount = [int(aa) for aa in input().strip().split(" ")]
forest = [[0 for _ in range(size)] for _ in range(size)]
for yy in range(size):
    for xx, ee in enumerate(input()):
        if ee == "*":
            forest[yy][xx] = 1
# forest = [[1 if ch == "*" else 0 for ch in input()] for _ in range(size)]
def clever():
    sumMap = [[0 for _ in range(size)] for _ in range(size)]
    sumMap[0][0] = forest[0][0] #1 if (0,0) in trees else 0
    for xx in range(1, size):
        sumMap[0][xx] = sumMap[0][xx-1] + forest[0][xx] #(1 if (xx,0) in trees else 0)
    for yy in range(1, size):
        sumMap[yy][0] = sumMap[yy-1][0] + forest[yy][0] #(1 if (0,yy) in trees else 0)
        for xx in range(1, size):
            sumMap[yy][xx] = (
                sumMap[yy-1][xx] 
                + sumMap[yy][xx-1] - sumMap[yy-1][xx-1] + forest[yy][xx]#(1 if (xx,yy) in trees else 0)
                )

    def getSubSum(startY,startX,endY,endX):
        # print(sumMap[endY][endX],endX,endY)
        # print(sumMap[startY][startX],startX,startY)
        ret = sumMap[endY][endX]
        if startY != 0:
            ret -= sumMap[startY-1][endX]
        if startX != 0:
            ret -= sumMap[endY][startX-1]
        if startY != 0 and startX != 0:
            ret += sumMap[startY-1][startX-1]
        return ret
    retArr = [0 for _ in range(queryCount)]
    for ii in range(queryCount):
        query = [int(aa)-1 for aa in input().strip().split(" ")]
        # if ii != 1:
        #     continue
        retArr[ii] = getSubSum(*query)
        # print(ret)
    return retArr
def stupid():
    for ii in range(queryCount):
        query = [int(aa)-1 for aa in input().strip().split(" ")]
        ret = 0
        for yy in range(query[0], query[2]+1):
            for xx in range(query[1], query[3]+1):
                ret += forest[yy][xx]
        # ret = getSubSum(*query)
        print(ret)

# stupid()

for ret in clever():
    print(ret)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED