Submission #898022

#	Time	Username	Problem	Language	Result	Execution time	Memory
898022		shrek27	Spiral (BOI16_spiral)	Cpython 3	27 / 100	1525 ms	3416 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 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

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)

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

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
            # print(x, y, num)
            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: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25