結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
|
提出日時 | 2023-05-06 13:00:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 440 ms / 3,000 ms |
コード長 | 1,398 bytes |
コンパイル時間 | 147 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 167,968 KB |
最終ジャッジ日時 | 2024-11-23 21:27:38 |
合計ジャッジ時間 | 10,000 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#BITを用いた実装 class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1) def sum(self, i): s = 0 while i > 0: s += self.tree[i] i -= i & -i return s def add(self, i, x): while i <= self.size: self.tree[i] += x i += i & -i def lower_bound(self,w): ''' a1+a2+...+ax>=wとなるような最小のxを求める https://algo-logic.info/binary-indexed-tree/ ''' if w<=0: return 0 else: x = 0 r = 1 while r < self.size: r = r<<1 lenth = r S = 0 while lenth > 0: if lenth + x < self.size and self.tree[x+lenth] < w: w -= self.tree[x+lenth] x += lenth lenth = lenth>>1 return x+1 Q,K = map(int,input().split()) query = [list(map(int,input().split())) for _ in range(Q)] V = set() for q in query: if q[0] == 1: V.add(q[1]) V = sorted(V) d = {v:i for i,v in enumerate(V)} bit = Bit(len(V)) for q in query: if q[0] == 1: bit.add(d[q[1]]+1,1) else: if bit.sum(len(V)) < K: print(-1) else: x = bit.lower_bound(K) print(V[x-1]) bit.add(x,-1)