oj.uz

Submission #898613

# Submission time Handle Problem Language Result Execution time Memory
898613 2024-01-04T23:26:47 Z shrek27 Spiral (BOI16_spiral) Python 3
27 / 100
 1500 ms 3356 KB 
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
    if y2 > x2:
        upper = (a + 1) * (8 * squaresSum(a + 1, y2) - 2 * linSum(a + 1, y2) + (2 - a) * (y2 - a)) // 2
        count += upper

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

def oneCorner(x2, y2):
    count = corner(x2, y2)
    col = 4 * squaresSum(1, y2) - linSum(1, y2) + y2
    row = 4 * squaresSum(1, x2) - 3 * linSum(1, x2) + x2
    count -= (col + row)
    count -= 1
    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)
    # if x1 == 1 and y1 == 1:
    # ar1 = oneCorner(x2, y2)
    # else:
    ar = func(x1, y1, x2, y2)
    print(ar)

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 3356 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3164 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 3356 KB Output is correct
2 Execution timed out 1515 ms 3164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1531 ms 3164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 3356 KB Output is correct
2 Correct 12 ms 3164 KB Output is correct
3 Execution timed out 1515 ms 3164 KB Time limit exceeded
4 Halted 0 ms 0 KB -