結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2019-07-23 18:30:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 412 ms / 3,000 ms |
コード長 | 1,491 bytes |
コンパイル時間 | 614 ms |
コンパイル使用メモリ | 82,520 KB |
実行使用メモリ | 161,812 KB |
最終ジャッジ日時 | 2024-06-26 05:46:26 |
合計ジャッジ時間 | 9,225 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
import sysinput = sys.stdin.readlineclass BIT:def __init__(self, n):self.n = nself.data = [0] * (n + 1)def ope(self, x, y):return x + ydef update(self, i, v):while i <= self.n:self.data[i] = self.ope(self.data[i], v)i += i & -idef query(self, i):ret = 0while 0 < i:ret = self.ope(self.data[i], ret)i &= i - 1return retdef lowerBound(self, w):if w <= 0: return 0x, k = 0, 2**self.n.bit_length()while k:if x+k <= self.n and self.data[x+k] < w:w -= self.data[x+k]x += kk >>= 1return x + 1def main():q, k = map(int, input().split())vs = set()query = []for i in range(q):s = input()if len(s) != 2:_, v = map(int, s.split())vs.add(v)query.append(v)else:query.append(-1)# 座圧, 1-indexedd = {}dd = {}for i, j in enumerate(sorted(list(vs))):d[j] = i+1dd[i+1] = j# BITn = len(d)B = BIT(n)for q in query:if q >= 0:p = d[q]B.update(p, 1)else:if B.query(n) >= k:a = B.lowerBound(k)print(dd[a])B.update(a, -1)else:print(-1)if __name__ == "__main__":main()