結果
問題 | No.992 最長増加部分列の数え上げ |
ユーザー |
![]() |
提出日時 | 2020-03-25 06:40:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 728 ms / 2,000 ms |
コード長 | 1,360 bytes |
コンパイル時間 | 214 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 176,672 KB |
最終ジャッジ日時 | 2025-01-01 19:36:59 |
合計ジャッジ時間 | 19,713 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
N=int(input()) A=list(map(int,input().split())) mod=10**9+7 compression_dict={a: ind+1 for ind, a in enumerate(sorted(set(A)))} A=[compression_dict[a] for a in A] def seg_function(x,y): # Segment treeで扱うfunction if x[0]==y[0]: return (x[0],x[1]+y[1]) elif x[0]>y[0]: return x else: return y seg_el=1<<(N.bit_length()) # Segment treeの台の要素数 SEG=[(-1,0)]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化 def update(n,x,seg_el): # A[n]をxへ更新(反映) i=n+seg_el SEG[i]=x i>>=1# 子ノードへ while i!=0: SEG[i]=seg_function(SEG[i*2],SEG[i*2+1]) i>>=1 def getvalues(l,r):# 区間[l,r)に関するseg_functionを調べる L=l+seg_el R=r+seg_el ANS=(-1,0) while L<R: if L & 1: ANS=seg_function(ANS , SEG[L]) L+=1 if R & 1: R-=1 ANS=seg_function(ANS , SEG[R]) L>>=1 R>>=1 return ANS update(0,(0,1),seg_el) for a in A: y=getvalues(a,a+1) z=getvalues(0,a) #print(a,x,y) if z[0]<y[0]: update(a,(y[0],z[1]+y[1]),seg_el) else: update(a,(z[0]+1,z[1]),seg_el) #for i in range(7): # print(getvalues(i,i+1),end=" ") #print() print(getvalues(0,N+1)[1]%mod)