Submission #898000

#	Time	Username	Problem	Language	Result	Execution time	Memory
898000		shrek27	Spiral (BOI16_spiral)	Cpython 3	15 / 100	1561 ms	3168 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 ** 2 - 1)

    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 intersection(x1, y1, x2, y2):
    pass

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)
            # print('x, a, b', x, a, b)
            # print((a + b) * (abs(a - b) + 1) // 2)
            # print(' ')
            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)

        if y > 0:
            a = max(x1, -y + 1)
            b = min(x2, y - 1)
        if a <= b:
            a = number(a, y)
            b = number(b, y)
            # print('y, a, b', y, a, b)
            # print((a + b) * (b - a + 1) // 2)
            # print(' ')
            count += (a + b) * (abs(b - a) + 1) // 2
            count = count % (10 ** 9 + 7)

    return count


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)
    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