結果
問題 |
No.3292 World Map Distance
|
ユーザー |
![]() |
提出日時 | 2025-10-10 02:19:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 748 ms / 3,000 ms |
コード長 | 3,064 bytes |
コンパイル時間 | 489 ms |
コンパイル使用メモリ | 82,752 KB |
実行使用メモリ | 228,396 KB |
最終ジャッジ日時 | 2025-10-10 02:20:08 |
合計ジャッジ時間 | 14,681 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sys input = sys.stdin.readline from collections import deque N,X0,Y0=map(int,input().split()) X=[] Y=[] for i in range(N): x,y=map(int,input().split()) X.append(x-1) Y.append(y-1) X.sort() LIST=[] for x in X: LIST.append((x+X0//2)%X0) LIST.append((x+X0//2+1)%X0) LIST=sorted(set(LIST)) ANS=0 now=0 LEFT=[] RIGHT=[] xx=LIST[0] for x in X: left=(xx-x)%X0 right=(x-xx)%X0 if left<=right: now+=left LEFT.append(x) else: now+=right RIGHT.append(x) LEFT.sort(key=lambda x:(xx-x)%X0,reverse=True) RIGHT.sort(key=lambda x:(x-xx)%X0) LEFT=deque(LEFT) RIGHT=deque(RIGHT) ANS=now #print(now,LEFT,RIGHT) for i in range(1,len(LIST)): mae=LIST[i-1] xx=LIST[i] now+=len(LEFT)*(LIST[i]-LIST[i-1])-len(RIGHT)*(LIST[i]-LIST[i-1]) #print(now) while RIGHT: x=RIGHT[0] if (x-mae)%X0<(xx-mae): RIGHT.popleft() now-=(x-mae)%X0-(xx-mae) LEFT.append(x) now+=(xx-x)%X0 else: break while LEFT: x=LEFT[0] left=(xx-x)%X0 right=(x-xx)%X0 #print("!",left,right) if right<=left: LEFT.popleft() RIGHT.append(x) now+=right-left else: break #print(now,LEFT,RIGHT) while RIGHT: x=RIGHT[0] left=(xx-x)%X0 right=(x-xx)%X0 if left<right: RIGHT.popleft() LEFT.append(x) now+=left-right else: break #print(xx,now,LEFT,RIGHT) ANS=max(ANS,now) X=Y X0=Y0 X.sort() LIST=[] for x in X: LIST.append((x+X0//2)%X0) LIST.append((x+X0//2+1)%X0) LIST=sorted(set(LIST)) ANS2=0 now=0 LEFT=[] RIGHT=[] xx=LIST[0] for x in X: left=(xx-x)%X0 right=(x-xx)%X0 if left<=right: now+=left LEFT.append(x) else: now+=right RIGHT.append(x) LEFT.sort(key=lambda x:(xx-x)%X0,reverse=True) RIGHT.sort(key=lambda x:(x-xx)%X0) LEFT=deque(LEFT) RIGHT=deque(RIGHT) ANS2=now #print(now,LEFT,RIGHT) for i in range(1,len(LIST)): mae=LIST[i-1] xx=LIST[i] now+=len(LEFT)*(LIST[i]-LIST[i-1])-len(RIGHT)*(LIST[i]-LIST[i-1]) #print(now) while RIGHT: x=RIGHT[0] if (x-mae)%X0<(xx-mae): RIGHT.popleft() now-=(x-mae)%X0-(xx-mae) LEFT.append(x) now+=(xx-x)%X0 else: break while LEFT: x=LEFT[0] left=(xx-x)%X0 right=(x-xx)%X0 #print("!",left,right) if right<=left: LEFT.popleft() RIGHT.append(x) now+=right-left else: break #print(now,LEFT,RIGHT) while RIGHT: x=RIGHT[0] left=(xx-x)%X0 right=(x-xx)%X0 if left<right: RIGHT.popleft() LEFT.append(x) now+=left-right else: break #print(xx,now,LEFT,RIGHT) ANS2=max(ANS2,now) print(ANS+ANS2)