結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2023-11-23 01:33:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,648 ms / 2,000 ms |
コード長 | 6,621 bytes |
コンパイル時間 | 450 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 158,080 KB |
最終ジャッジ日時 | 2024-09-26 07:49:23 |
合計ジャッジ時間 | 23,214 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import bisectimport copyimport decimalimport fractionsimport heapqimport itertoolsimport mathimport randomimport sysimport timefrom collections import Counter,deque,defaultdictfrom functools import lru_cache,reducefrom heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_maxdef _heappush_max(heap,item):heap.append(item)heapq._siftdown_max(heap, 0, len(heap)-1)def _heappushpop_max(heap, item):if heap and item < heap[0]:item, heap[0] = heap[0], itemheapq._siftup_max(heap, 0)return itemfrom math import gcd as GCDread=sys.stdin.readreadline=sys.stdin.readlinereadlines=sys.stdin.readlineswrite=sys.stdout.write#import pypyjit#pypyjit.set_param('max_unroll_recursion=-1')#sys.set_int_max_str_digits(10**9)class Segment_Tree:def __init__(self,N,f,e,lst=None,dynamic=False):self.f=fself.e=eself.N=Nif dynamic:self.segment_tree=defaultdict(lambda:self.e)else:if lst==None:self.segment_tree=[self.e]*2*self.Nelse:assert len(lst)<=self.Nself.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst))for i in range(self.N-1,0,-1):self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])def __getitem__(self,i):if type(i)==int:if -self.N<=i<0:return self.segment_tree[i+self.N*2]elif 0<=i<self.N:return self.segment_tree[i+self.N]else:raise IndexError("list index out of range")else:a,b,c=i.start,i.stop,i.stepif a==None:a=self.Nelse:a+=self.Nif b==None:b=self.N*2else:b+=self.Nreturn self.segment_tree[slice(a,b,c)]def __setitem__(self,i,x):if -self.N<=i<0:i+=self.N*2elif 0<=i<self.N:i+=self.Nelse:raise IndexError("list index out of range")self.segment_tree[i]=xwhile i>1:i>>= 1self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])def Build(self,lst):for i,x in enumerate(lst,self.N):self.segment_tree[i]=xfor i in range(self.N-1,0,-1):self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])def Fold(self,L=None,R=None):if L==None:L=self.Nelse:L+=self.Nif R==None:R=self.N*2else:R+=self.NvL=self.evR=self.ewhile L<R:if L&1:vL=self.f(vL,self.segment_tree[L])L+=1if R&1:R-=1vR=self.f(self.segment_tree[R],vR)L>>=1R>>=1return self.f(vL,vR)def Fold_Index(self,L=None,R=None):if L==None:L=self.Nelse:L+=self.Nif R==None:R=self.N*2else:R+=self.Nif L==R:return Nonex=self.Fold(L-self.N,R-self.N)while L<R:if L&1:if self.segment_tree[L]==x:i=LbreakL+=1if R&1:R-=1if self.segment_tree[R]==x:i=RbreakL>>=1R>>=1while i<self.N:if self.segment_tree[i]==self.segment_tree[i<<1]:i<<=1else:i<<=1i|=1i-=self.Nreturn idef Bisect_Right(self,L=None,f=None):if L==self.N:return self.Nif L==None:L=0L+=self.Nvl=self.evr=self.el,r=L,self.N*2while l<r:if l&1:vl=self.f(vl,self.segment_tree[l])l+=1if r&1:r-=1vr=self.f(self.segment_tree[r],vr)l>>=1r>>=1if f(self.f(vl,vr)):return self.Nv=self.ewhile True:while L%2==0:L>>=1vv=self.f(v,self.segment_tree[L])if f(vv):v=vvL+=1else:while L<self.N:L<<=1vv=self.f(v,self.segment_tree[L])if f(vv):v=vvL+=1return L-self.Ndef Bisect_Left(self,R=None,f=None):if R==0:return 0if R==None:R=self.NR+=self.Nvl=self.evr=self.el,r=self.N,Rwhile l<r:if l&1:vl=self.f(vl,self.segment_tree[l])l+=1if r&1:r-=1vr=self.f(self.segment_tree[r],vr)l>>=1r>>=1if f(self.f(vl,vr)):return 0v=self.ewhile True:R-=1while R>1 and R%2:R>>=1vv=self.f(self.segment_tree[R],v)if f(vv):v=vvelse:while R<self.N:R=2*R+1vv=self.f(self.segment_tree[R],v)if f(vv):v=vvR-=1return R+1-self.Ndef __str__(self):return "["+", ".join(map(str,self.segment_tree[self.N:]))+"]"def Compress(lst):decomp=sorted(list(set(lst)))comp={x:i for i,x in enumerate(decomp)}return comp,decompN=int(readline())A=list(map(int,readline().split()))comp,decomp=Compress(A)le=len(comp)L=Segment_Tree(le,lambda x,y:x+y,0)R=Segment_Tree(le,lambda x,y:x+y,0)for a in A:R[comp[a]]+=1inf=1<<60ans=inffor i in range(N):R[comp[A[i]]]-=1Ll=min(comp[A[i]],L.Bisect_Right(0,lambda x:x==0))Rl=min(comp[A[i]],R.Bisect_Right(0,lambda x:x==0))if not comp[A[i]] in (Ll,Rl):ans=min(ans,decomp[Ll]+A[i]+decomp[Rl])Lr=L.Bisect_Right(comp[A[i]]+1,lambda x:x==0)Rr=R.Bisect_Right(comp[A[i]]+1,lambda x:x==0)if not le in (Lr,Rr):ans=min(ans,decomp[Lr]+A[i]+decomp[Rr])L[comp[A[i]]]+=1if ans==inf:ans=-1print(ans)