結果
問題 | No.1188 レベルX門松列 |
ユーザー | Kazun |
提出日時 | 2021-05-19 13:03:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 862 ms / 2,000 ms |
コード長 | 5,365 bytes |
コンパイル時間 | 188 ms |
コンパイル使用メモリ | 82,420 KB |
実行使用メモリ | 134,512 KB |
最終ジャッジ日時 | 2024-10-09 17:13:22 |
合計ジャッジ時間 | 9,956 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 209 ms
93,488 KB |
testcase_01 | AC | 656 ms
111,660 KB |
testcase_02 | AC | 577 ms
108,236 KB |
testcase_03 | AC | 726 ms
116,380 KB |
testcase_04 | AC | 511 ms
133,772 KB |
testcase_05 | AC | 39 ms
53,192 KB |
testcase_06 | AC | 142 ms
92,800 KB |
testcase_07 | AC | 433 ms
111,148 KB |
testcase_08 | AC | 433 ms
111,328 KB |
testcase_09 | AC | 39 ms
54,864 KB |
testcase_10 | AC | 41 ms
55,108 KB |
testcase_11 | AC | 214 ms
79,604 KB |
testcase_12 | AC | 219 ms
79,488 KB |
testcase_13 | AC | 224 ms
80,392 KB |
testcase_14 | AC | 587 ms
110,112 KB |
testcase_15 | AC | 862 ms
134,512 KB |
testcase_16 | AC | 116 ms
77,528 KB |
testcase_17 | AC | 685 ms
124,012 KB |
testcase_18 | AC | 41 ms
54,668 KB |
testcase_19 | AC | 653 ms
123,280 KB |
testcase_20 | AC | 39 ms
54,260 KB |
testcase_21 | AC | 38 ms
53,660 KB |
testcase_22 | AC | 38 ms
53,960 KB |
testcase_23 | AC | 39 ms
53,980 KB |
ソースコード
class Segment_Tree(): """ このプログラム内は1-index """ def __init__(self,L,calc,unit,index): """calcを演算とするリストLのSegment Treeを作成 calc:演算(2変数関数,モノイド) unit:モノイドcalcの単位元 (xe=ex=xを満たすe) index:数列の第1要素のindex """ self.calc=calc self.unit=unit self.index=index N=len(L) d=max(1,(N-1).bit_length()) k=1<<d self.data=[unit]*k+L+[unit]*(k-len(L)) self.N=k self.depth=d for i in range(k-1,0,-1): self.data[i]=self.calc(self.data[i<<1],self.data[i<<1|1]) def get(self,k,index=1): """第k要素を取得 """ assert 0<=k-index<self.N,"添字が範囲外" return self.data[k-index+self.N] def update(self,k,x,index=1): """第k要素をxに変え,更新を行う. k:数列の要素 x:更新後の値 """ assert 0<=k-index<self.N,"添字が範囲外" m=(k-index)+self.N self.data[m]=x while m>1: m>>=1 self.data[m]=self.calc(self.data[m<<1],self.data[m<<1|1]) def product(self,From,To,index=1,left_closed=True,right_closed=True): L=(From-index)+self.N+(not left_closed) R=(To-index)+self.N+(right_closed) vL=self.unit vR=self.unit while L<R: if L&1: vL=self.calc(vL,self.data[L]) L+=1 if R&1: R-=1 vR=self.calc(self.data[R],vR) L>>=1 R>>=1 return self.calc(vL,vR) def all_product(self): return self.data[1] def max_right(self,left,cond,index=1): """以下の2つをともに満たすxの1つを返す.\n (1) x=left or cond(data[left]*data[left+1]*...*data[x-1]):True (2) x=N+index or cond(data[left]*data[left+1]*...*data[x]):False ※condが単調減少の時,cond(data[left]*...*data[x-1])を満たす最大のxとなる. cond:関数(引数が同じならば結果も同じ) cond(unit):True index<=left<=r<n+index """ left-=index assert 0<=left<=self.N,"添字が範囲外" assert cond(self.unit),"単位元が条件を満たさない." if left==self.N: return self.N+index left+=self.N-(index-1) sm=self.unit calc=self.calc first=True while first or (left & (-left))!=left: first=False while left%2==0: left>>=1 if not cond(calc(sm,self.data[left])): while left<self.N: left<<=1 if cond(self.calc(sm,self.data[left])): sm=self.calc(sm,self.data[left]) left+=1 return left-self.N+index sm=self.calc(sm,self.data[left]) left+=1 return self.N+index def min_left(self,right,cond,index=1): """以下の2つをともに満たすyの1つを返す.\n (1) y=right or cond(data[y]*data[y+1]*...*data[right]):True (2) y=index or cond(data[y-1]*data[y]*...*data[right]):False ※condが単調減少の時,cond(data[y]*...*data[right-1])を満たす最大のyとなる. cond:関数(引数が同じならば結果も同じ) cond(unit):True index<=left<=r<n+index """ right-=index assert 0<=right<=self.N,"添字が範囲外" assert cond(self.unit),"単位元が条件を満たさない." if right==0: return index right+=self.N sm=self.unit calc=self.calc first=1 while first or (right & (-right))!=right: first=0 right-=1 while right>1 and right&1: right>>=1 if not cond(calc(self.data[right],sm)): while right<self.N: right=2*right+1 if cond(calc(self.data[right],sm)): sm=calc(self.data[right],sm) right-=1 return right+1-self.N+index sm=calc(self.data[right],sm) return index def __getitem__(self,k): return self.get(k,self.index) def __setitem__(self,k,x): return self.update(k,x,self.index) #================================================== def LIS(X): T=[0]*N inf=float("inf") S=Segment_Tree([-inf]*B_len,max,0,0) for i in range(N): j=I[X[i]] if j>0: T[i]=S.product(0,j-1,0) else: T[i]=0 S.update(j,T[i]+1,0) return T def LDS(X): T=[0]*N inf=float("inf") S=Segment_Tree([-inf]*B_len,max,0,0) for i in range(N): j=I[X[i]] if j<B_len-1: T[i]=S.product(j+1,B_len-1,0) else: T[i]=0 S.update(j,T[i]+1,0) return T #================================================== N=int(input()) A=list(map(int,input().split())) B=sorted(set(A)) B_len=len(B) I={B[i]:i for i in range(len(B))} P=LIS(A) Q=LIS(A[::-1])[::-1] R=[min(p,q) for p,q in zip(P,Q)] S=LDS(A) T=LDS(A[::-1])[::-1] U=[min(s,t) for s,t in zip(S,T)] print(max(R+U))