0
0 комментариев

Задание заключается в том, чтобы для матрицы NxM, где N, M < 1000, просуммировать K (K < 100000) наборов элементов, заключенных в прямоугольнике, углы которого задаются координатами (x1, x2, y1, y2).

То есть для матрицы

1 2 3
2 4 6
7 8 9

и координат (1, 2, 1, 3) это будет прямоугольник

1 2
2 4
7 8

Мой код работает, но недостаточно быстро (самые объемные тесты в системе не укладываются во время), numpy использовать нельзя. Есть ли какие-то способы ускорить выполнение?

def build_y(cx, fx, lx, cy, fy, ly):
    if fy == ly:
        if fx == lx:
            t[cx][cy] = a[fx][fy]
        else:
            t[cx][cy] = t[cx*2][cy] + t[cx*2+1][cy];
    else:
        my = int((fy + ly) / 2)
        build_y (cx, fx, lx, cy*2, fy, my)
        build_y (cx, fx, lx, cy*2+1, my+1, ly)
        t[cx][cy] = t[cx][cy*2] + t[cx][cy*2+1]
 
def build_x(cx, fx, lx):
    if fx != lx:
        mx = int((fx + lx) / 2)
        build_x (cx*2, fx, mx)
        build_x (cx*2+1, mx+1, lx)
    build_y (cx, fx, lx, 1, 0, m-1)
 
def sum_y (cx, cy, tfy, tly, fy, ly):
    if fy > ly:
        return 0
    if fy == tfy and tly == ly:
        return t[cx][cy]
    tmy = int((tfy + tly) / 2)
    return sum_y(cx, cy*2, tfy, tmy, fy, min(ly, tmy)) + sum_y(cx, cy*2+1, tmy+1, tly, max(fy, tmy+1), ly)
 
def sum_x(cx, tfx, tlx, fx, lx, fy, ly):
    if fx > lx:
        return 0
    if fx == tfx and tlx == lx:
        return sum_y(cx, 1, 0, m-1, fy, ly)
    tmx = int((tfx + tlx) / 2)
    return sum_x(cx*2, tfx, tmx, fx, min(lx, tmx), fy, ly) + sum_x(cx*2+1, tmx+1, tlx, max(fx, tmx+1), lx, fy, ly)
 
fin = open('input.txt', 'r').read().split()
n = int(fin[0])
m = int(fin[1])
k = int(fin[2])
a = []
b = []
t = [0]*4*n
for i in range(4*n):
    t[i] = [0]*4*m
for i in range(n):
    a.append([int(j) for j in fin[3+i*m:3+i*m+m]])
build_x(1, 0, n-1)
for i in range(k):
    b.append([int(j) for j in fin [3+n*m+4*i:3+n*m+4*i+4]])
for i in range(k):
    print(sum_x(1, 0, n-1, b[i][0]-1, b[i][2]-1, b[i][1]-1, b[i][3]-1))


Добавить комментарий