結果

問題 No.1997 X Lighting
ユーザー lam6er
提出日時 2025-03-31 17:35:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,311 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 137,200 KB
最終ジャッジ日時 2025-03-31 17:36:18
合計ジャッジ時間 6,130 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff #

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1

    D = set()
    S = set()
    for _ in range(M):
        x = int(input[idx])
        idx += 1
        y = int(input[idx])
        idx += 1
        d = x - y
        s = x + y
        D.add(d)
        S.add(s)

    # Calculate sum_A
    sum_A = 0
    for d in D:
        sum_A += N - abs(d)

    # Calculate sum_B
    sum_B = 0
    for s in S:
        if s <= N + 1:
            sum_B += s - 1
        else:
            sum_B += 2 * N + 1 - s

    # Prepare even and odd lists
    even_s = []
    odd_s = []
    for s in S:
        if s % 2 == 0:
            even_s.append(s)
        else:
            odd_s.append(s)
    even_s.sort()
    odd_s.sort()

    # Calculate intersection
    intersection = 0
    for d in D:
        L = max(d + 2, 2 - d)
        R = 2 * N - d
        if L > R:
            continue
        parity = d % 2
        if parity == 0:
            lst = even_s
        else:
            lst = odd_s

        left = bisect.bisect_left(lst, L)
        right = bisect.bisect_right(lst, R)
        intersection += (right - left)

    total = sum_A + sum_B - intersection
    print(total)

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