Submission #898688

#	Time	Username	Problem	Language	Result	Execution time	Memory
898688		shrek27	Spiral (BOI16_spiral)	Cpython 3	100 / 100	14 ms	3520 KiB

spiral

def squaresSum(a, b):
    f = lambda n : n * (n + 1) * (2 * n + 1) // 6
    return f(b) - f(a - 1)

def cubeSum(a, b):
    f = lambda n : (n * (n + 1) // 2) ** 2
    return f(b) - f(a - 1)

def linSum(a, b):
    return (a + b) * (b - a + 1) // 2

def corner(x2, y2):
    a = min(x2, y2)
    count = 0
    count += 8 * cubeSum(1, a) + a + 1
    count = count % (10 ** 9 + 7)
    if y2 > x2:
        upper = (a + 1) * (8 * squaresSum(a + 1, y2) - 2 * linSum(a + 1, y2) + (2 - a) * (y2 - a)) // 2
        count += upper
        count = count % (10 ** 9 + 7)

    elif x2 > y2:
        right = (a + 1) * (8 * squaresSum(a + 1, x2) - 6 * linSum(a + 1, x2) + (2 + a) * (x2 - a)) // 2
        count += right
        count = count % (10 ** 9 + 7)
    return count

def oneOneCorner(x2, y2):
    # top right
    if x2 < 1 or y2 < 1:
        return 0

    count = corner(x2, y2)
    col = (4 * squaresSum(1, y2) - linSum(1, y2) + y2) % (10 ** 9 + 7)
    row = (4 * squaresSum(1, x2) - 3 * linSum(1, x2) + x2) % (10 ** 9 + 7)
    count -= (col + row)
    count -= 1
    return count % (10 ** 9 + 7)

def oneZeroCorner(x2, y2):
    # bottom right
    if x2 < 1 or y2 > 0:
        return 0

    x2, y2 = abs(x2) - 1, abs(y2)
    a = min(x2, y2)
    count = 0
    count += 8 * cubeSum(0, a) + 12 * squaresSum(0, a) + 8 * linSum(0, a) + 2 * (a + 1)

    if x2 > y2:
        right = (a + 1) * (8 * squaresSum(a + 1, x2) + 10 * linSum(a + 1, x2) + (4 - a) * (x2 - a)) // 2
        count += right
    elif y2 > x2:
        down = (a + 1) * (8 * squaresSum(a + 1, y2) + 6 * linSum(a + 1, y2) + (4 + a) * (y2 - a)) // 2
        count += down

    count = count % (10 ** 9 + 7)
    return count


def zeroZeroCorner(x2, y2):
    # bottom left
    if x2 > 0 or y2 > 0:
        return 0

    x2, y2 = abs(x2), abs(y2)
    a = min(x2, y2)
    count = 0
    count += 8 * cubeSum(0, a) + 8 * squaresSum(0, a) + 4 * linSum(0, a) + (a + 1)

    if x2 > y2:
        left = (a + 1) * (8 * squaresSum(a + 1, x2) + 2 * linSum(a + 1, x2) + (2 + a) * (x2 - a)) // 2
        count += left
    elif y2 > x2:
        down = (a + 1) * (8 * squaresSum(a + 1, y2) + 6 * linSum(a + 1, y2) + (2 - a) * (y2 - a)) // 2
        count += down

    count = count % (10 ** 9 + 7)
    return count


def negOneZero(x2, y2):
    # top left
    if x2 > -1 or y2 < 1:
        return 0

    x2, y2 = abs(x2) - 1, abs(y2) - 1
    a = min(x2, y2)
    count = 0
    count += 8 * cubeSum(0, a) + 20 * squaresSum(0, a) + 18 * linSum(0, a) + 5 * (a + 1)

    if x2 > y2:
        left = (a + 1) * (8 * squaresSum(a + 1, x2) + 18 * linSum(a + 1, x2) + (10 - a) * (x2 - a)) // 2
        count += left
    elif y2 > x2:
        top = (a + 1) * (8 * squaresSum(a + 1, y2) + 14 * linSum(a + 1, y2) + (10 + a) * (y2 - a)) // 2
        count += top

    count = count % (10 ** 9 + 7)
    return count


def middleColumn(y2):
    if y2 < 1:
        return 0

    # the columb betwee the top corners (cuz they dont fit closely)
    count = 4 * squaresSum(1, y2) - linSum(1, y2) + y2
    return count % (10 ** 9 + 7)


n, q = input().split(' ')
n, q = int(n), int(q)


def partition(x1, y1, x2, y2):
    # 1 - top righ quarter, 2 - bottom right quarter, 3 - bottom left quarter, 4 - top left quarter. x, y - bottom left corner of each part, X, Y - top right
    count = 0
    p1 = oneOneCorner(x2, y2) - oneOneCorner(x1 - 1, y2) - oneOneCorner(x2, y1 - 1) + oneOneCorner(x1 - 1, y1 - 1)
    p2 = oneZeroCorner(x2, y1) - oneZeroCorner(x2, y2 + 1) - oneZeroCorner(x1 - 1, y1) + oneZeroCorner(x1 - 1, y2 + 1)
    p3 = zeroZeroCorner(x1, y1) - zeroZeroCorner(x1, y2 + 1) - zeroZeroCorner(x2 + 1, y1) + zeroZeroCorner(x2 + 1, y2 + 1)
    p4 = negOneZero(x1, y2) - negOneZero(x2 + 1, y2) - negOneZero(x1, y1 - 1) + negOneZero(x2 + 1, y1 - 1)
    col = 0
    if 0 in range(x1, x2 + 1):
        col += middleColumn(y2) - middleColumn(y1 - 1)

    count += p1 + p2 + p3 + p4 + col

    count = count % (10 ** 9 + 7)
    return count


for i in range(q):
    x = input()
    x1, y1, x2, y2 = x.split(' ')
    x1, y1, x2, y2 = int(x1), int(y1), int(x2), int(y2)
    area = partition(x1, y1, x2, y2)

    print(area)

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25