結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー |
![]() |
提出日時 | 2024-02-23 22:14:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 506 ms / 2,500 ms |
コード長 | 1,182 bytes |
コンパイル時間 | 393 ms |
コンパイル使用メモリ | 82,180 KB |
実行使用メモリ | 228,072 KB |
最終ジャッジ日時 | 2024-09-29 06:59:38 |
合計ジャッジ時間 | 15,048 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
import sysinput = sys.stdin.readlineN,A=map(int,input().split())X=list(map(int,input().split()))T=int(input())LR=[list(map(int,input().split())) for i in range(T)]LIST=[]for x in X:LIST.append(x)for l,r in LR:LIST.append(l)LIST.append(r)S=sorted(set(LIST))D={S[i]:i for i in range(len(S))}for i in range(N):X[i]=D[X[i]]for i in range(T):LR[i][0]=D[LR[i][0]]LR[i][1]=D[LR[i][1]]seg_el=1<<((max(X)+1).bit_length()) # Segment treeの台の要素数SEG=[-1]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化def getvalue(n,seg_el): # 一点の値を取得i=n+seg_elANS=-1ANS=max(SEG[i],ANS)i>>=1# 子ノードへwhile i!=0:ANS=max(SEG[i],ANS)i>>=1return ANSdef updates(l,r,x): # 区間[l,r)のminを更新.L=l+seg_elR=r+seg_elwhile L<R:if L & 1:SEG[L]=max(x,SEG[L])L+=1if R & 1:R-=1SEG[R]=max(x,SEG[R])L>>=1R>>=1for i in range(T):l,r=LR[i]updates(l,r+1,i+1)for i in range(N):print(getvalue(X[i],seg_el))