結果
問題 |
No.1997 X Lighting
|
ユーザー |
![]() |
提出日時 | 2022-07-03 04:57:38 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 683 ms / 2,000 ms |
コード長 | 1,305 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 23,452 KB |
最終ジャッジ日時 | 2024-11-28 13:02:53 |
合計ジャッジ時間 | 11,611 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sys input = sys.stdin.readline import bisect ODD_1=[] ODD_2=[] EVEN_1=[] EVEN_2=[] ANS=0 def calc1(x): if x<N: return x+1 else: return N-(x-N+1) def calc2(x): if x>=0: return N-x else: return N+x N,M=map(int,input().split()) for i in range(M): x,y=map(int,input().split()) x-=1 y-=1 if (x+y)%2==0: u=y+x v=x-y EVEN_1.append(u) EVEN_2.append(v) else: u=y+x v=x-y ODD_1.append(u) ODD_2.append(v) EVEN_1=sorted(set(sorted(EVEN_1))) EVEN_2=sorted(set(sorted(EVEN_2))) ODD_1=sorted(set(sorted(ODD_1))) ODD_2=sorted(set(sorted(ODD_2))) ANS=0 for x in ODD_1+EVEN_1: ANS+=calc1(x) for x in ODD_2+EVEN_2: ANS+=calc2(x) # ODD_1でx<Nと交わるのは、ODD_2で-x<=x # ODD_1でx>=Nと交わるのは、k=x-N+1として、ODD_2で-(x-2*k)<=x-2*k for x in ODD_1: if x<N: y=x else: k=x-N+1 y=(x-2*k) l=bisect.bisect_left(ODD_2,-y) r=bisect.bisect_right(ODD_2,y) ANS-=r-l for x in EVEN_1: if x<N: y=abs(x) else: k=x-N+1 y=abs(x-2*k) l=bisect.bisect_left(EVEN_2,-y) r=bisect.bisect_right(EVEN_2,y) ANS-=r-l print(ANS)