結果
問題 |
No.1997 X Lighting
|
ユーザー |
![]() |
提出日時 | 2022-07-01 23:23:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 940 bytes |
コンパイル時間 | 296 ms |
コンパイル使用メモリ | 82,184 KB |
実行使用メモリ | 169,364 KB |
最終ジャッジ日時 | 2024-11-26 07:20:58 |
合計ジャッジ時間 | 6,167 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
N, M = map(int, input().split()) n = N - 1 pp = set() mm = set() ans = 0 for _ in range(M): x, y = map(int, input().split()) x -= 1 y -= 1 p = x + y m = x - y if p not in pp: pp.add(p) ans += N - abs(p - n) if m not in mm: mm.add(m) ans += N - abs(m) pp = sorted(pp) mm = sorted(mm) pp = sorted([n - abs(n - a) for a in pp]) mm = sorted([abs(a) for a in mm]) ppe = [a for a in pp if a % 2 == 0] ppo = [a for a in pp if a % 2 == 1] mme = [a for a in mm if a % 2 == 0] mmo = [a for a in mm if a % 2 == 1] def calc(pp, mm): SS = sorted(set(pp + mm)) IA = {a: i for i, a in enumerate(SS)} pp = [IA[a] for a in pp] mm = [IA[a] for a in mm] C = [0] * (len(SS) + 1) for a in mm: C[a] += 1 for i in range(len(SS)): C[i+1] += C[i] ret = 0 for a in pp: ret += C[a] return ret ans -= calc(ppe, mme) + calc(ppo, mmo) print(ans)