제출 #898618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898618		shrek27	Spiral (BOI16_spiral)	Cpython 3	15 / 100	221 ms	3676 KiB

spiral

def number(x, y):
    if x == y and x >= 0:
        num = 1 + (2 * x - 1) * 2 * x
    elif x == y and x < 0:
        x = abs(x)
        num = 1 + (2 * x + 1) * 2 * x
    elif y == -x and x < 0:
        x = abs(x)
        num = 1 + 4 * x ** 2
    elif y == -x + 1 and x >=1:
        num = 1 + (2 * x - 1) ** 2

    elif y > x and y > -x:
        num = number(y, y) + y - x

    elif y < x and y > -x + 1:
        num = number(x, x) + y - x

    elif y < -x + 1 and y < x:
        num = number(y, y) + x - y

    elif y < -x and y > x:
        num = number(x, x) + x - y

    return num

def func(x1, y1, x2, y2):
    count = 0
    for x in range(x1, x2 + 1):
        if x <= 0:
            a = min(-x, y2)
            b = max(x, y1)

        if x > 0:
            a = min(x, y2)
            b = max(-x + 1, y1)

        if a >= b:
            a = number(x, a)
            b = number(x, b)
            count += (a + b) * (abs(a - b)+ 1) // 2
            count = count % (10 ** 9 + 7)

    for y in range(y1, y2 + 1):
        if y <= 0:
            a = max(x1, y + 1)
            b = min(x2, -y)

        elif y > 0:
            a = max(x1, -y + 1)
            b = min(x2, y - 1)

        else:
            break

        if a <= b:
            a = number(a, y)
            b = number(b, y)
            count += (a + b) * (abs(b - a) + 1) // 2
            count = count % (10 ** 9 + 7)

    return count

def check(x1, y1, x2, y2):
    count = 0
    for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
            num = number(x, y)
            count += num
            count = count % (10 ** 9 + 7)
    return count

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 oneCorner(x2, y2):
    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)

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

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)
    if x1 == 1 and y1 == 1:
        ar1 = oneCorner(x2, y2)
    else:
        ar = func(x1, y1, x2, y2)
    print(ar)

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