結果

問題 No.2809 Sort Query
ユーザー hirayuu_yc
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import deque
from array import array
import sys
input=sys.stdin.readline
class FenwickTree:
def __init__(self,size):
self.tree=array("i",[0]*(size+1))
self.size=size
self.start=size.bit_length()-1
def add(self,pos,val):
pos+=1
while pos<=self.size:
self.tree[pos]+=val
pos+=pos&-pos
def bisect(self,pos):
now=0
val=0
for i in range(self.start,-1,-1):
if now+(1<<i)<=self.size and val+self.tree[now+(1<<i)]<=pos:
now+=1<<i
val+=self.tree[now]
return now
N,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]]=i
a=FenwickTree(len(press))
for i in range(N):
A[i]=ser[A[i]]
a.add(A[i],1)
change=[-1]*N
chq=deque()
changed=set()
for i in range(Q):
t,*q=query[i]
if t==1:
k,x=q
x=ser[x]
change[k-1]=x
changed.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]])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0