結果
問題 | No.2809 Sort Query |
ユーザー |
|
提出日時 | 2024-04-21 18:34:30 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,539 bytes |
コンパイル時間 | 245 ms |
コンパイル使用メモリ | 81,980 KB |
実行使用メモリ | 261,780 KB |
最終ジャッジ日時 | 2024-07-12 20:54:54 |
合計ジャッジ時間 | 57,098 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 53 WA * 18 |
ソースコード
from collections import dequefrom array import arrayimport sysinput=sys.stdin.readlineclass FenwickTree:def __init__(self,size):self.tree=array("i",[0]*(size+1))self.size=sizeself.start=size.bit_length()-1def add(self,pos,val):pos+=1while pos<=self.size:self.tree[pos]+=valpos+=pos&-posdef bisect(self,pos):now=0val=0for i in range(self.start,-1,-1):if now+(1<<i)<=self.size and val+self.tree[now+(1<<i)]<=pos:now+=1<<ival+=self.tree[now]return nowN,Q=map(int,input().split())A=list(map(int,input().split()))query=[tuple(map(int,input().split())) for i in range(Q)]press=A[:]for i in range(Q):if query[i][0]==1:press.append(query[i][2])press.sort()ser={}for i in range(len(press)):ser[press[i]]=ia=FenwickTree(len(press))for i in range(N):A[i]=ser[A[i]]a.add(A[i],1)change=[-1]*Nchq=deque()changed=set()for i in range(Q):t,*q=query[i]if t==1:k,x=qx=ser[x]change[k-1]=xchanged.add(k-1)if t==2:for j in changed:chq.append((a.bisect(j),change[j]))change[j]=-1;changed.clear()while chq:a.add(chq[-1][0],-1)a.add(chq[-1][1],1)chq.pop()if t==3:k=q[0]if change[k-1]==-1:print(press[a.bisect(k-1)])else:print(press[change[k-1]])