結果

問題 No.1997 X Lighting
ユーザー lam6er
提出日時 2025-03-26 15:50:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 283 ms / 2,000 ms
コード長 1,889 bytes
コンパイル時間 311 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 144,932 KB
最終ジャッジ日時 2025-03-26 15:51:16
合計ジャッジ時間 6,429 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    
    D = set()
    S = set()
    buttons = []
    for _ in range(M):
        x = int(input[ptr])
        y = int(input[ptr+1])
        ptr +=2
        d = x - y
        s = x + y
        D.add(d)
        S.add(s)
        buttons.append((d, s))
    
    # Calculate A: sum of lengths for D
    A = 0
    for d in D:
        A += N - abs(d)
    
    # Calculate B: sum of lengths for S
    B = 0
    for s in S:
        lower = max(1, s - N)
        upper = min(N, s - 1)
        if lower > upper:
            continue
        B += upper - lower + 1
    
    # Preprocess D for C calculation
    d_list = sorted(D)
    # Prepare parity cumulative arrays
    par0 = [0] * (len(d_list) + 1)
    par1 = [0] * (len(d_list) + 1)
    for i in range(len(d_list)):
        d = d_list[i]
        par0[i+1] = par0[i]
        par1[i+1] = par1[i]
        if d % 2 == 0:
            par0[i+1] += 1
        else:
            par1[i+1] += 1
    
    # Calculate C
    C = 0
    for s in S:
        s_p = s % 2
        # Compute d_min and d_max
        d_min = max(2 - s, s - 2 * N)
        d_max = min(2 * N - s, s - 2)
        if d_min > d_max:
            continue
        
        # Find indices in d_list for [d_min, d_max]
        left_idx = bisect.bisect_left(d_list, d_min)
        right_idx = bisect.bisect_right(d_list, d_max) - 1
        
        if left_idx > right_idx:
            continue  # no d in this range
        
        # Calculate number of d with parity s_p in this range
        if s_p == 0:
            count = par0[right_idx + 1] - par0[left_idx]
        else:
            count = par1[right_idx + 1] - par1[left_idx]
        
        C += count
    
    print(A + B - C)

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