結果

問題 No.325 マンハッタン距離2
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:55:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 1,000 ms
コード長 3,737 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 54,456 KB
最終ジャッジ日時 2025-03-26 15:56:03
合計ジャッジ時間 2,145 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def count_quadrant1(x1, x2, y1, y2, d):
    a = max(x1, 0)
    b = min(x2, d)
    if a > b:
        return 0
    c = max(y1, 0)
    y2_upper = y2
    x_end_new = min(b, d - c)
    if a > x_end_new:
        return 0
    split_point = d - y2_upper
    part1_start = a
    part1_end = min(x_end_new, split_point)
    part2_start = max(a, split_point + 1)
    part2_end = x_end_new
    total = 0
    if part1_start <= part1_end:
        count_y = max(0, y2_upper - c + 1)
        if count_y > 0:
            num_x = part1_end - part1_start + 1
            total += num_x * count_y
    if part2_start <= part2_end:
        s = part2_start
        t = part2_end
        first = d - c + 1 - s
        last = d - c + 1 - t
        count = (first + last) * (t - s + 1) // 2
        if count > 0:
            total += count
    return total

def count_quadrant2(x1, x2, y1, y2, d):
    a = max(x1, -d)
    b = min(x2, -1)
    if a > b:
        return 0
    c = max(y1, 0)
    y2_upper = y2
    x_start = max(a, c - d)
    x_end = b
    if x_start > x_end:
        return 0
    split_point = y2_upper - d
    part1_start = x_start
    part1_end = min(x_end, split_point)
    part2_start = max(x_start, split_point + 1)
    part2_end = x_end
    total = 0
    if part1_start <= part1_end:
        s = part1_start
        t = part1_end
        first = (d - c + 1) + s
        last = (d - c + 1) + t
        count = (first + last) * (t - s + 1) // 2
        total += count
    if part2_start <= part2_end:
        count_y = max(0, y2_upper - c + 1)
        if count_y > 0:
            num_x = part2_end - part2_start + 1
            total += num_x * count_y
    return total

def count_quadrant3(x1, x2, y1, y2, d):
    a = max(x1, -d)
    b = min(x2, -1)
    if a > b:
        return 0
    y_lower = y1
    y_upper = min(y2, -1)
    if y_lower > y_upper:
        return 0
    x_start = max(a, -d - y_upper)
    x_end = b
    if x_start > x_end:
        return 0
    split_point = -d - y_lower
    part1_start = x_start
    part1_end = min(x_end, split_point)
    part2_start = max(x_start, split_point + 1)
    part2_end = x_end
    total = 0
    if part1_start <= part1_end:
        s = part1_start
        t = part1_end
        first = y_upper + d + s + 1
        last = y_upper + d + t + 1
        count = (first + last) * (t - s + 1) // 2
        total += count
    if part2_start <= part2_end:
        count_y = y_upper - y_lower + 1
        if count_y > 0:
            num_x = part2_end - part2_start + 1
            total += num_x * count_y
    return total

def count_quadrant4(x1, x2, y1, y2, d):
    a = max(x1, 0)
    b = min(x2, d)
    if a > b:
        return 0
    y_lower = y1
    y_upper = min(y2, -1)
    if y_lower > y_upper:
        return 0
    x_end = min(b, d + y_upper)
    if a > x_end:
        return 0
    split_point = d + y_lower
    part1_start = a
    part1_end = min(x_end, split_point - 1)
    part2_start = max(a, split_point)
    part2_end = x_end
    total = 0
    if part1_start <= part1_end:
        count_y = max(0, y_upper - y_lower + 1)
        if count_y > 0:
            num_x = part1_end - part1_start + 1
            total += num_x * count_y
    if part2_start <= part2_end:
        s = part2_start
        t = part2_end
        first = y_upper + d - s + 1
        last = y_upper + d - t + 1
        count = (first + last) * (t - s + 1) // 2
        total += count
    return total

def main():
    x1, y1, x2, y2, d = map(int, input().split())
    total = 0
    total += count_quadrant1(x1, x2, y1, y2, d)
    total += count_quadrant2(x1, x2, y1, y2, d)
    total += count_quadrant3(x1, x2, y1, y2, d)
    total += count_quadrant4(x1, x2, y1, y2, d)
    print(total)

if __name__ == "__main__":
    main()
0