結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 るさ
|
| 提出日時 | 2020-12-22 15:00:14 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,077 bytes |
| コンパイル時間 | 424 ms |
| コンパイル使用メモリ | 82,180 KB |
| 実行使用メモリ | 101,596 KB |
| 最終ジャッジ日時 | 2024-09-21 14:11:11 |
| 合計ジャッジ時間 | 6,298 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 56 ms
74,752 KB |
| testcase_01 | AC | 58 ms
68,864 KB |
| testcase_02 | AC | 56 ms
69,376 KB |
| testcase_03 | AC | 524 ms
84,480 KB |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
ソースコード
class Order_Set:
def __init__(self, deep:int):
self.deep = deep
self.length = 2 ** (deep+1) -1
self.value = [0] * self.length
self.used = [False] * self.length
self.free = [0] * self.length
self.capacity = [0] * self.length
for i in range(2 ** deep -1, self.length):
self.free[i] = 1
self.capacity[i] = 1
for i in range(2 ** deep -2, -1, -1):
self.free[i] = self.free[2*i+1] + self.free[2*i+2] + 1
self.capacity[i] = self.free[i]
def insert(self, value:int, x=0, min_over=True):
f = (False,)
if self.free[x] == 0:
if min_over:
m = self.min_pop(x)
f = (True, min(value, m))
value = max(value, m)
else:
m = self.max_pop(x)
f = (True, max(value, m))
value = min(value, m)
if not self.used[x]:
self.used[x] = True
self.value[x] = value
t = x*2+1
while t != 0:
t = (t-1) // 2
self.free[t] -= 1
return f
if value == self.value[x]:
return f
elif value > self.value[x]:
r = self.insert(value, x*2+2, True)
if r[0]:
t = self.value[x]
self.value[x] = r[1]
self.insert(t, x*2+1)
return f
else:
r = self.insert(value, x*2+1, False)
if r[0]:
t = self.value[x]
self.value[x] = r[1]
self.insert(t, x*2+2)
return f
def min_pop(self, x:int):
if x*2+1 >= self.length:
r = self.value[x]
self.used[x] = False
x = x*2+1
while x != 0:
x = (x-1) // 2
self.free[x] += 1
return r
if self.used[x*2+1]:
return self.min_pop(x*2+1)
r = self.value[x]
if self.used[x*2+2]:
self.value[x] = self.min_pop(x*2+2)
else:
self.used[x] = False
x = x*2+1
while x != 0:
x = (x-1) // 2
self.free[x] += 1
return r
def max_pop(self, x:int):
if x*2+1 >= self.length:
r = self.value[x]
self.used[x] = False
x = x*2+1
while x != 0:
x = (x-1) // 2
self.free[x] += 1
return r
if self.used[x*2+2]:
return self.max_pop(x*2+2)
r = self.value[x]
if self.used[x*2+1]:
self.value[x] = self.max_pop(x*2+1)
else:
self.used[x] = False
x = x*2+1
while x != 0:
x = (x-1) // 2
self.free[x] += 1
return r
def erase(self, value:int):
x = 0
while True:
if x >= self.length or not self.used[x]:
return
if self.value[x] > value:
x = x*2+1
elif self.value[x] < value:
x = x*2+2
if self.value[x] == value:
if x*2+1 < self.length:
le = not self.used[x*2+1]
re = not self.used[x*2+2]
else:
le = True
re = True
if le and re:
self.used[x] = False
x = x*2+1
while x != 0:
x = (x-1) // 2
self.free[x] += 1
elif le:
self.value[x] = self.min_pop(x*2+2)
else:
self.value[x] = self.max_pop(x*2+1)
return
def lower_bound(self, v:int, x=0):
if x >= self.length or not self.used[x]:
return None
s = set([self.value[x]])
ll = self.lower_bound(v, x*2+1)
rl = self.lower_bound(v, x*2+1)
if not ll is None:
s.add(ll)
if not rl is None:
s.add(rl)
return min(s)
def isin(self, v:int):
return lower_bound(v) == v
def index(self, id:int, x=0):
if x*2+1 >= self.length:
if id == 0:
return self.value[x]
else:
raise IndexError("set index out of range")
if not self.used[x]:
raise IndexError("set index out of range")
lp = self.capacity[x*2+1] - self.free[x*2+1]
if id == lp:
return self.value[x]
elif id < lp:
return self.index(id, x*2+1)
else:
return self.index(id-lp-1, x*2+2)
q,k = map(int, input().split())
os = Order_Set(17)
for qi in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
os.insert((query[1], qi))
else:
if os.capacity[0] - os.free[0] >= k:
r = os.index(k-1)
print(r[0])
os.erase(r)
else:
print(-1)