結果
問題 | No.2248 max(C)-min(C) |
ユーザー | 👑 Kazun |
提出日時 | 2023-03-18 01:25:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 955 ms / 3,000 ms |
コード長 | 4,997 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 81,896 KB |
実行使用メモリ | 134,784 KB |
最終ジャッジ日時 | 2023-10-18 16:49:48 |
合計ジャッジ時間 | 15,322 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
53,628 KB |
testcase_01 | AC | 37 ms
53,628 KB |
testcase_02 | AC | 37 ms
53,628 KB |
testcase_03 | AC | 51 ms
66,236 KB |
testcase_04 | AC | 49 ms
64,188 KB |
testcase_05 | AC | 46 ms
61,604 KB |
testcase_06 | AC | 66 ms
72,936 KB |
testcase_07 | AC | 66 ms
72,876 KB |
testcase_08 | AC | 65 ms
72,932 KB |
testcase_09 | AC | 65 ms
72,860 KB |
testcase_10 | AC | 47 ms
61,604 KB |
testcase_11 | AC | 66 ms
72,868 KB |
testcase_12 | AC | 52 ms
66,172 KB |
testcase_13 | AC | 60 ms
70,800 KB |
testcase_14 | AC | 65 ms
72,932 KB |
testcase_15 | AC | 67 ms
72,940 KB |
testcase_16 | AC | 52 ms
66,236 KB |
testcase_17 | AC | 66 ms
72,872 KB |
testcase_18 | AC | 278 ms
122,140 KB |
testcase_19 | AC | 95 ms
81,916 KB |
testcase_20 | AC | 312 ms
134,540 KB |
testcase_21 | AC | 299 ms
134,784 KB |
testcase_22 | AC | 234 ms
115,592 KB |
testcase_23 | AC | 174 ms
102,780 KB |
testcase_24 | AC | 110 ms
85,348 KB |
testcase_25 | AC | 286 ms
128,972 KB |
testcase_26 | AC | 274 ms
120,116 KB |
testcase_27 | AC | 284 ms
122,892 KB |
testcase_28 | AC | 89 ms
80,972 KB |
testcase_29 | AC | 278 ms
120,912 KB |
testcase_30 | AC | 152 ms
94,888 KB |
testcase_31 | AC | 320 ms
134,616 KB |
testcase_32 | AC | 115 ms
86,624 KB |
testcase_33 | AC | 140 ms
92,528 KB |
testcase_34 | AC | 315 ms
134,628 KB |
testcase_35 | AC | 311 ms
134,608 KB |
testcase_36 | AC | 323 ms
134,556 KB |
testcase_37 | AC | 196 ms
106,900 KB |
testcase_38 | AC | 295 ms
125,748 KB |
testcase_39 | AC | 297 ms
125,796 KB |
testcase_40 | AC | 299 ms
125,740 KB |
testcase_41 | AC | 271 ms
121,880 KB |
testcase_42 | AC | 296 ms
125,804 KB |
testcase_43 | AC | 274 ms
123,568 KB |
testcase_44 | AC | 297 ms
126,072 KB |
testcase_45 | AC | 252 ms
119,056 KB |
testcase_46 | AC | 167 ms
99,948 KB |
testcase_47 | AC | 294 ms
125,792 KB |
testcase_48 | AC | 497 ms
126,932 KB |
testcase_49 | AC | 947 ms
133,580 KB |
testcase_50 | AC | 955 ms
133,584 KB |
testcase_51 | AC | 949 ms
133,580 KB |
testcase_52 | AC | 947 ms
133,584 KB |
testcase_53 | AC | 194 ms
85,324 KB |
ソースコード
class Segment_Tree(): def __init__(self, L, calc, unit): """ calc を演算とするリスト L の Segment Tree を作成 calc: 演算 (2変数関数, Monoid) unit: Monoid calc の単位元 (xe=ex=xを満たすe) """ self.calc=calc self.unit=unit N=len(L); self.n=N d=max(1,(N-1).bit_length()) k=1<<d self.data=data=[unit]*k+L+[unit]*(k-len(L)) self.N=k self.depth=d for i in range(k-1,0,-1): data[i]=calc(data[i<<1], data[i<<1|1]) def get(self, k): """ 第 k 要素を取得 """ assert 0<=k<self.N,"添字が範囲外" return self.data[k+self.N] def update(self, k, x): """第k要素をxに変え,更新を行う. k:数列の要素 x:更新後の値 """ assert 0<=k<self.N,"添字が範囲外" m=k+self.N data=self.data; calc=self.calc data[m]=x while m>1: m>>=1 data[m]=calc(data[m<<1], data[m<<1|1]) def product(self, l, r, left_closed=True,right_closed=True): L=l+self.N+(not left_closed) R=r+self.N+(right_closed) vL=self.unit vR=self.unit data=self.data; calc=self.calc while L<R: if L&1: vL=calc(vL, data[L]) L+=1 if R&1: R-=1 vR=calc(data[R], vR) L>>=1 R>>=1 return calc(vL,vR) def all_product(self): return self.data[1] def max_right(self, left, cond): """ 以下の2つをともに満たす x の1つを返す.\n (1) r=left or cond(data[left]*data[left+1]*...*data[r-1]): True (2) r=N or cond(data[left]*data[left+1]*...*data[r]): False ※ cond が単調減少の時, cond(data[left]*...*data[r-1]) を満たす最大の r となる. cond:関数(引数が同じならば結果も同じ) cond(unit): True 0<=left<=N """ assert 0<=left<=self.N,"添字が範囲外" assert cond(self.unit),"単位元が条件を満たさない." if left==self.N: return self.N left+=self.N sm=self.unit calc=self.calc; data=self.data first=True while first or (left & (-left))!=left: first=False while left%2==0: left>>=1 if not cond(calc(sm, data[left])): while left<self.N: left<<=1 if cond(calc(sm, data[left])): sm=calc(sm, data[left]) left+=1 return left-self.N sm=calc(sm, data[left]) left+=1 return self.N def min_left(self, right, cond): """ 以下の2つをともに満たす y の1つを返す.\n (1) l=right or cond(data[l]*data[l+1]*...*data[right-1]): True (2) l=0 or cond(data[l-1]*data[l]*...*data[right-1]): False ※ cond が単調増加の時, cond(data[l]*...*data[right-1]) を満たす最小の l となる. cond: 関数(引数が同じならば結果も同じ) cond(unit): True 0<=right<=N """ assert 0<=right<=self.N,"添字が範囲外" assert cond(self.unit),"単位元が条件を満たさない." if right==0: return 0 right+=self.N sm=self.unit calc=self.calc; data=self.data first=1 while first or (right & (-right))!=right: first=0 right-=1 while right>1 and right&1: right>>=1 if not cond(calc(data[right], sm)): while right<self.N: right=2*right+1 if cond(calc(data[right], sm)): sm=calc(data[right], sm) right-=1 return right+1-self.N sm=calc(data[right], sm) return 0 def __getitem__(self,k): return self.get(k) def __setitem__(self,k,x): return self.update(k,x) def __iter__(self): for i in range(self.n): yield self.get(i) #================================================== def solve(): N=int(input()) A=list(map(int,input().split())) B=list(map(int,input().split())) M=[sorted([A[i],B[i], (A[i]+B[i])//2]) for i in range(N)] S=Segment_Tree([(B[i],i) for i in range(N)], max, (-1, 0)) C_min=10**10 for i in range(N): y=M[i].pop() S.update(i, (y,i)) C_min=min(C_min, y) ans=10**10 while True: x,i=S.all_product() if M[i]: y=M[i].pop() C_min=min(C_min,y) S.update(i,(y,i)) ans=min(ans, S.all_product()[0]-C_min) else: break return ans #================================================== print(solve())