結果
問題 | 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 sys input = sys.stdin.readline N,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_el ANS=-1 ANS=max(SEG[i],ANS) i>>=1# 子ノードへ while i!=0: ANS=max(SEG[i],ANS) i>>=1 return ANS def updates(l,r,x): # 区間[l,r)のminを更新. L=l+seg_el R=r+seg_el while L<R: if L & 1: SEG[L]=max(x,SEG[L]) L+=1 if R & 1: R-=1 SEG[R]=max(x,SEG[R]) L>>=1 R>>=1 for 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))