Problem p03707 (python)

Fixed submission:
import gc


class Ruiseki2D():
    """二次元累積和を構築する
    構築O(HW), 区間取得クエリO(1)
    """
    def __init__(self, matrix):
        self.h = len(matrix)
        self.w = len(matrix[0])
        self.ruiseki = [[0] * (self.w + 1) for _ in range(self.h + 1)]

        for i in range(self.h):
            for j in range(self.w):
                self.ruiseki[i + 1][j + 1] = self.ruiseki[i + 1][j] + matrix[i][j]
        for i in range(self.h):
            for j in range(self.w):
                self.ruiseki[i + 1][j + 1] += self.ruiseki[i][j + 1]

    def get_sum(self, hl, hr, wl, wr):
        """[hl, hr), [wl, wr) で囲まれた部分の和を求める"""
        return self.ruiseki[hr][wr] + self.ruiseki[hl][wl] - self.ruiseki[hr][wl] - self.ruiseki[hl][wr]


n, m, q = map(int, input().split())
s = [list(map(int, input())) for i in range(n)]
query = [list(map(int, input().split())) for i in range(q)]

ru_col_cnt = Ruiseki2D(s)

# メモリ削減のため累積和配列を使い回す
yoko_edge = [[0] * (m + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(m - 1):
        if s[i][j] == 1 and s[i][j + 1] == 1:
            yoko_edge[i + 1][j + 1] = 1
for i in range(n):
    for j in range(m):
        yoko_edge[i + 1][j + 1] += yoko_edge[i + 1][j]
for i in range(n):
    for j in range(m):
        yoko_edge[i + 1][j + 1] += yoko_edge[i][j + 1]

tate_edge = [[0] * (m + 1) for i in range(n + 1)]
for i in range(n - 1):
    for j in range(m):
        if s[i][j] == 1 and s[i + 1][j] == 1:
            tate_edge[i + 1][j + 1] = 1
for i in range(n):
    for j in range(m):
        tate_edge[i + 1][j + 1] += tate_edge[i + 1][j]
for i in range(n):
    for j in range(m):
        tate_edge[i + 1][j + 1] += tate_edge[i][j + 1]



def yoko_get_sum(hl, hr, wl, wr):
    return yoko_edge[hr][wr] + yoko_edge[hl][wl] - yoko_edge[hr][wl] - yoko_edge[hl][wr]
  
def tate_get_sum(hl, hr, wl, wr):
    return tate_edge[hr][wr] + tate_edge[hl][wl] - tate_edge[hr][wl] - tate_edge[hl][wr]

for hl, wl, hr, wr in query:
    hl, wl = hl - 1, wl - 1
    ans = ru_col_cnt.get_sum(hl, hr, wl, wr)
    ans -= yoko_get_sum(hl, hr, wl, wr - 1) + tate_get_sum(hl, hr - 1, wl, wr)
    print(ans)

Buggy submission (verdict: Runtime Error):
class Ruiseki2D():
    def __init__(self, matrix):
        self.h = len(matrix)
        self.w = len(matrix[0])
        self.ruiseki = [[0] * (self.w + 1) for _ in range(self.h + 1)]

        for i in range(self.h):
            for j in range(self.w):
                self.ruiseki[i + 1][j + 1] = self.ruiseki[i + 1][j] + matrix[i][j]
        for i in range(self.h):
            for j in range(self.w):
                self.ruiseki[i + 1][j + 1] += self.ruiseki[i][j + 1]

    def get_sum(self, hl, hr, wl, wr):
        """[hl, hr), [wl, wr)"""
        return self.ruiseki[hr][wr] + self.ruiseki[hl][wl] - self.ruiseki[hr][wl] - self.ruiseki[hl][wr]


n, m, q = map(int, input().split())
s = [list(input()) for i in range(n)]
for i in range(n):
    for j in range(n):
        s[i][j] = int(s[i][j])

matrix = [[1 if s[i][j] == 1 else 0 for j in range(m)] for i in range(n)]
ruiseki = Ruiseki2D(matrix)

matrix = [[0]*m for i in range(n)]
for i in range(n):
    for j in range(m - 1):
        if s[i][j] == 1 and s[i][j + 1] == 1:
            matrix[i][j] = 1
ruiseki_w = Ruiseki2D(matrix)

matrix = [[0]*m for i in range(n)]
for i in range(n - 1):
    for j in range(m):
        if s[i][j] == 1 and s[i + 1][j] == 1:
            matrix[i][j] = 1
ruiseki_h = Ruiseki2D(matrix)

for i in range(q):
    hl, wl, hr, wr = list(map(int, input().split()))
    hl -= 1
    wl -= 1
    print(ruiseki.get_sum(hl, hr, wl, wr) - ruiseki_w.get_sum(hl, hr, wl, wr - 1) - ruiseki_h.get_sum(hl, hr - 1, wl, wr))

Buggy submission (verdict: Runtime Error):
class Ruiseki2D():
    def __init__(self, matrix):
        self.h = len(matrix)
        self.w = len(matrix[0])
        self.ruiseki = [[0] * (self.w + 1) for _ in range(self.h + 1)]

        for i in range(self.h):
            for j in range(self.w):
                self.ruiseki[i + 1][j + 1] = self.ruiseki[i + 1][j] + matrix[i][j]
        for i in range(self.h):
            for j in range(self.w):
                self.ruiseki[i + 1][j + 1] += self.ruiseki[i][j + 1]

    def get_sum(self, hl, hr, wl, wr):
        """[hl, hr), [wl, wr)"""
        return self.ruiseki[hr][wr] + self.ruiseki[hl][wl] - self.ruiseki[hr][wl] - self.ruiseki[hl][wr]


n, m, q = map(int, input().split())
s = [list(input()) for i in range(n)]
for i in range(n):
    for j in range(n):
        s[i][j] = int(s[i][j])

matrix = [[1 if s[i][j] == 1 else 0 for j in range(m)] for i in range(n)]
ruiseki = Ruiseki2D(matrix)

matrix_w = [[0]*m for i in range(n)]
for i in range(n):
    for j in range(m - 1):
        if s[i][j] == 1 and s[i][j + 1] == 1:
            matrix_w[i][j] = 1
ruiseki_w = Ruiseki2D(matrix_w)

matrix_h = [[0]*m for i in range(n)]
for i in range(n - 1):
    for j in range(m):
        if s[i][j] == 1 and s[i + 1][j] == 1:
            matrix_h[i][j] = 1
ruiseki_h = Ruiseki2D(matrix_h)

for i in range(q):
    hl, wl, hr, wr = list(map(int, input().split()))
    hl -= 1
    wl -= 1
    print(ruiseki.get_sum(hl, hr, wl, wr) - ruiseki_w.get_sum(hl, hr, wl, wr - 1) - ruiseki_h.get_sum(hl, hr - 1, wl, wr))

Buggy submission (verdict: Runtime Error):
class Ruiseki2D():
    def __init__(self, matrix):
        self.h = len(matrix)
        self.w = len(matrix[0])
        self.ruiseki = [[0] * (self.w + 1) for _ in range(self.h + 1)]

        for i in range(self.h):
            for j in range(self.w):
                self.ruiseki[i + 1][j + 1] = self.ruiseki[i + 1][j] + matrix[i][j]
        for i in range(self.h):
            for j in range(self.w):
                self.ruiseki[i + 1][j + 1] += self.ruiseki[i][j + 1]

    def get_sum(self, hl, hr, wl, wr):
        """[hl, hr), [wl, wr)"""
        return self.ruiseki[hr][wr] + self.ruiseki[hl][wl] - self.ruiseki[hr][wl] - self.ruiseki[hl][wr]


n, m, q = map(int, input().split())
s = [list(input()) for i in range(n)]
query = [list(map(int, input().split())) for i in range(q)]
for i in range(n):
    for j in range(n):
        s[i][j] = int(s[i][j])

matrix = [[1 if s[i][j] == 1 else 0 for j in range(m)] for i in range(n)]
ruiseki = Ruiseki2D(matrix)

matrix_w = [[0]*m for i in range(n)]
for i in range(n):
    for j in range(m - 1):
        if s[i][j] == 1 and s[i][j + 1] == 1:
            matrix_w[i][j] = 1
ruiseki_w = Ruiseki2D(matrix_w)

matrix_h = [[0]*m for i in range(n)]
for i in range(n - 1):
    for j in range(m):
        if s[i][j] == 1 and s[i + 1][j] == 1:
            matrix_h[i][j] = 1
ruiseki_h = Ruiseki2D(matrix_h)

for i in range(q):
    hl, wl, hr, wr = query[i]
    hl -= 1
    wl -= 1
    print(ruiseki.get_sum(hl, hr, wl, wr) - ruiseki_w.get_sum(hl, hr, wl, wr - 1) - ruiseki_h.get_sum(hl, hr - 1, wl, wr))