結果
問題 |
No.1997 X Lighting
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()