Submission #24372271

Source Code Expand

def calc(n, a1, b1, a2, b2):
    s = max(a1, a2)
    t = min(a1 + n // b1, a2 + n // b2) + 1
    if s >= t: return 0
    S = [s, t]
    if b1 != b2:
        x = (a1 * b1 - a2 * b2) // (b1 - b2)
        if s <= x <= t:
            S.append(x)
        x = ((a1 - 1) * b1 - (a2 - 1) * b2) // (b1 - b2)
        if s <= x <= t:
            S.append(x)
        x = (a2 * b2 - a1 * b1 + b1) // (b2 - b1)
        if s <= x <= t:
            S.append(x)
        x = (a1 * b1 - a2 * b2 + b2) // (b1 - b2)
        if s <= x <= t:
            S.append(x)
        
    
    T = {s, t}
    for a in S:
        for d in range(-2, 3):
            b = a + d
            if s <= b <= t:
                T.add(b)
    X = sorted(T)
    # print("X =", X)
    
    re = 0
    for x, y in zip(X, X[1:]):
        k = x
        l = max((k - a1) * b1, (k - a2) * b2, 1)
        r = min((k - a1 + 1) * b1, (k - a2 + 1) * b2, n + 1)
        z1 = max(r - l, 0)
        k = y - 1
        l = max((k - a1) * b1, (k - a2) * b2, 1)
        r = min((k - a1 + 1) * b1, (k - a2 + 1) * b2, n + 1)
        z2 = max(r - l, 0)
        re += (z1 + z2) * (y - x) // 2
    return re

T = int(input())
for _ in range(T):
    n, a1, b1, a2, b2 = map(int, input().split())
    print(calc(n, a1, b1, a2, b2))

Submission Info

Submission Time
Task E - Training
User Kiri8128
Language PyPy3 (7.3.0)
Score 700
Code Size 1306 Byte
Status AC
Exec Time 1363 ms
Memory 86060 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 1
AC × 31
Set Name Test Cases
Sample 01_sample_01.txt
All 01_sample_01.txt, 02_rand_mix_01.txt, 02_rand_mix_02.txt, 02_rand_mix_03.txt, 02_rand_mix_04.txt, 02_rand_mix_05.txt, 02_rand_mix_06.txt, 02_rand_mix_07.txt, 02_rand_mix_08.txt, 02_rand_mix_09.txt, 02_rand_mix_10.txt, 02_rand_mix_11.txt, 02_rand_mix_12.txt, 02_rand_mix_13.txt, 02_rand_mix_14.txt, 02_rand_mix_15.txt, 03_non_trivial_only_01.txt, 03_non_trivial_only_02.txt, 03_non_trivial_only_03.txt, 03_non_trivial_only_04.txt, 03_non_trivial_only_05.txt, 03_non_trivial_only_06.txt, 03_non_trivial_only_07.txt, 03_non_trivial_only_08.txt, 03_non_trivial_only_09.txt, 03_non_trivial_only_10.txt, 03_non_trivial_only_11.txt, 03_non_trivial_only_12.txt, 03_non_trivial_only_13.txt, 03_non_trivial_only_14.txt, 03_non_trivial_only_15.txt
Case Name Status Exec Time Memory
01_sample_01.txt AC 67 ms 61860 KiB
02_rand_mix_01.txt AC 1298 ms 85340 KiB
02_rand_mix_02.txt AC 1322 ms 82752 KiB
02_rand_mix_03.txt AC 1339 ms 85952 KiB
02_rand_mix_04.txt AC 1363 ms 83816 KiB
02_rand_mix_05.txt AC 1345 ms 83080 KiB
02_rand_mix_06.txt AC 1343 ms 83164 KiB
02_rand_mix_07.txt AC 1340 ms 86060 KiB
02_rand_mix_08.txt AC 1334 ms 80256 KiB
02_rand_mix_09.txt AC 1336 ms 82176 KiB
02_rand_mix_10.txt AC 1318 ms 85440 KiB
02_rand_mix_11.txt AC 1350 ms 84488 KiB
02_rand_mix_12.txt AC 1349 ms 82344 KiB
02_rand_mix_13.txt AC 1322 ms 83276 KiB
02_rand_mix_14.txt AC 1333 ms 81792 KiB
02_rand_mix_15.txt AC 1322 ms 81400 KiB
03_non_trivial_only_01.txt AC 1317 ms 80392 KiB
03_non_trivial_only_02.txt AC 1312 ms 80544 KiB
03_non_trivial_only_03.txt AC 1307 ms 79832 KiB
03_non_trivial_only_04.txt AC 1298 ms 77116 KiB
03_non_trivial_only_05.txt AC 1309 ms 79184 KiB
03_non_trivial_only_06.txt AC 1315 ms 80432 KiB
03_non_trivial_only_07.txt AC 1335 ms 80096 KiB
03_non_trivial_only_08.txt AC 1311 ms 81564 KiB
03_non_trivial_only_09.txt AC 1253 ms 82352 KiB
03_non_trivial_only_10.txt AC 1256 ms 78848 KiB
03_non_trivial_only_11.txt AC 1333 ms 79776 KiB
03_non_trivial_only_12.txt AC 1297 ms 78360 KiB
03_non_trivial_only_13.txt AC 1294 ms 80920 KiB
03_non_trivial_only_14.txt AC 1307 ms 78948 KiB
03_non_trivial_only_15.txt AC 1316 ms 81616 KiB