結果
問題 |
No.1997 X Lighting
|
ユーザー |
|
提出日時 | 2022-07-01 23:54:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 280 ms / 2,000 ms |
コード長 | 1,323 bytes |
コンパイル時間 | 432 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 95,328 KB |
最終ジャッジ日時 | 2024-11-26 08:02:10 |
合計ジャッジ時間 | 6,546 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
from bisect import bisect_left import sys int1 = lambda x: int(x) - 1 # input = lambda: sys.stdin.buffer.readline() input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) i1 = lambda: int1(input()) mi = lambda: map(int, input().split()) mi1 = lambda: map(int1, input().split()) li = lambda: list(mi()) li1 = lambda: list(mi1()) lli = lambda n: [li() for _ in range(n)] INF = float("inf") mod = int(1e9 + 7) # mod = 998244353 n, m = mi() down = set() left_down = set() left_up = set() bottom_up = set() for _ in range(m): y, x = mi() if y <= x: down.add(x - y) else: left_down.add(y - x) if y + x <= n + 1: left_up.add(y + x) else: bottom_up.add(y + x - n - 1) ans = 0 for x in down: ans += n - x for y in left_down: ans += n - y for y in left_up: ans += y - 1 for x in bottom_up: ans += n - x def oe(s): res = [[], []] for x in s: res[x & 1].append(x) res[0].sort() res[1].sort() return res d = oe(down) ld = oe(left_down) lu = oe(left_up) bu = oe(bottom_up) for y in left_up: ans -= bisect_left(d[y & 1], y) ans -= bisect_left(ld[y & 1], y) for y in left_down: ans -= bisect_left(bu[(n + 1 - y) & 1], n - y) for x in down: ans -= bisect_left(bu[(x & 1) ^ (~n & 1)], n - x) print(ans)