結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
|
提出日時 | 2022-11-02 00:00:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 465 ms / 3,000 ms |
コード長 | 1,217 bytes |
コンパイル時間 | 372 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 155,952 KB |
最終ジャッジ日時 | 2024-07-16 11:32:57 |
合計ジャッジ時間 | 10,710 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
class Fenwick: def __init__(self, n): self.size = n self.node = [0 for _ in range(n + 2)] def add(self, i, x): i += 1 while i <= self.size: self.node[i] += x i += (i & (- i)) def sum(self, i): i = min(i, n) ans = 0 while i > 0: ans += self.node[i] i -= (i & (- i)) return ans def prod(self, l, r): return self.sum(r) - self.sum(l) def bisect_left(self, c): if c <= 0: return 0 else: ans = 0 l = 1 << (self.size.bit_length()) while l > 0: if ans + l <= self.size and self.node[ans + l] < c: c -= self.node[ans + l] ans += l l >>= 1 if ans == self.size: return None else: return ans q, k = map(int, input().split()) queries = [list(map(int, input().split())) for _ in range(q)] xs = set() for t, *args in queries: if t == 1: xs.add(args[0]) xs = sorted(list(xs)) idx = {} for i in range(len(xs)): idx[xs[i]] = i ft = Fenwick(len(xs)) for t, *args in queries: if t == 1: i = idx[args[0]] ft.add(i, 1) elif t == 2: i = ft.bisect_left(k) if i is None: print("-1") else: print(xs[i]) ft.add(i, -1)