結果
問題 | No.2436 Min Diff Distance |
ユーザー |
👑 ![]() |
提出日時 | 2023-08-17 01:24:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,093 ms / 2,000 ms |
コード長 | 1,509 bytes |
コンパイル時間 | 268 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 103,728 KB |
最終ジャッジ日時 | 2024-11-25 18:28:03 |
合計ジャッジ時間 | 16,802 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
class seg: def __init__(self,n,e,f): self.size=1 self.e=e self.f=f while self.size<n: self.size*=2 self.v=[self.e]*(self.size*2) def set(self,ind,val): ind+=self.size self.v[ind]=self.f(self.v[ind],val) while ind!=1: ind//=2 self.v[ind]=self.f(self.v[ind*2],self.v[ind*2+1]) def clear(self): for i in range(self.size*2):self.v[i]=self.e def prod(self,l,r): l+=self.size r+=self.size res=self.e while l<r: if l&1: res=self.f(res,self.v[l]) l+=1 if r&1: r-=1 res=self.f(res,self.v[r]) l>>=1;r>>=1 return res N=int(input()) X=[0]*N;Y=[0]*N for i in range(N): X[i],Y[i]=map(int,input().split()) P=[0]*N;Q=[N+N]*N A=0;B=N*N;C=-N;D=N for i in range(N): A=max(A,X[i]+Y[i]) B=min(B,X[i]+Y[i]) C=max(C,X[i]-Y[i]) D=min(D,X[i]-Y[i]) for i in range(N): P[i]=max(A-X[i]-Y[i],X[i]+Y[i]-B,Y[i]-X[i]+C,X[i]-Y[i]-D) p=seg(N,-N-N,max) order=[0]*N def f(a): return X[a] for i in range(N): order[i]=i order.sort(key=f) for rp in range(4): for i in range(N): X[i]=N+1-X[i] order.reverse() if rp&1: for i in range(N): Y[i]=N+1-Y[i] p.clear() for a in order: Q[a]=min(Q[a],X[a]+Y[a]-p.prod(0,Y[a])) p.set(Y[a]-1,Y[a]+X[a]) for i in range(N): P[i]-=Q[i] print(min(P))