cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/library-checker/data-structure/double_ended_priority_queue.test.py
- View this file on GitHub
- Last update: 2025-08-24 20:27:05+09:00
- Problem: https://judge.yosupo.jp/problem/double_ended_priority_queue
Depends on
- cp_library/alg/dp/max2_fn.py
- cp_library/ds/heap/interval_heap_cls.py
- cp_library/ds/list/elist_fn.py
- cp_library/ds/list/reserve_fn.py
- cp_library/io/fast_io_fn.py
- cp_library/io/io_base_cls.py
- cp_library/io/io_cls.py
Code
# verification-helper: PROBLEM https://judge.yosupo.jp/problem/double_ended_priority_queue
def main():
N, Q = rd()
S = rdl(N)
reserve(S, N+Q)
heap = IntervalHeap(S)
for _ in range(Q):
t = rd()
if t[0] == 0: heap.push(t[1])
elif t[0] == 1: wtn(heap.pop_min())
else: wtn(heap.pop_max())
from cp_library.ds.heap.interval_heap_cls import IntervalHeap
from cp_library.ds.list.reserve_fn import reserve
from cp_library.io.fast_io_fn import rd, rdl, wtn
if __name__ == '__main__':
main()# verification-helper: PROBLEM https://judge.yosupo.jp/problem/double_ended_priority_queue
def main():
N, Q = rd()
S = rdl(N)
reserve(S, N+Q)
heap = IntervalHeap(S)
for _ in range(Q):
t = rd()
if t[0] == 0: heap.push(t[1])
elif t[0] == 1: wtn(heap.pop_min())
else: wtn(heap.pop_max())
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
class IntervalHeap:
def __init__(heap, arr: list):
heap._d = arr
for k in range(len(arr)): heap._up(k)
def push(heap, item):
heap._d.append(item)
heap._up(len(heap._d)-1)
def pop_min(heap):
item = heap._d.pop()
if heap._d: item, heap._d[0] = heap._d[0], item; heap._down(0)
return item
def pop_max(heap):
item = heap._d.pop()
if len(heap._d) >= 2: item, heap._d[1] = heap._d[1], item; heap._down(1)
return item
def _up(heap, k):
v = heap._d[k]
if k&1 and heap._d[k] < heap._d[k-1]: heap._d[k] = heap._d[k-1]; k ^= 1
while 0 <= (p := (k>>1)-1&~1) and v < heap._d[p]: heap._d[k], k = heap._d[p], p
while 0 <= (p := (k>>1)-1|1) and heap._d[p] < v: heap._d[k], k = heap._d[p], p
heap._d[k] = v
def _down(heap, k):
n, v, rt = len(d := heap._d)-2, d[k], k
if k & 1: # max heap
c = 2*k+1
while c < n and v < d[c := c+2 if d[c] < d[c+2] else c]: d[k], k, c = d[c], c, c<<1|1
if c < n+2 and v < d[c]: d[k], k = d[c], c
d[k] = v
if v < d[k-1]:
d[k] = d[k-1]; k ^= 1
while rt <= (p := (k>>1)-1&~1) and v < d[p]: d[k], k = d[p], p
d[k] = v
else: # min heap
c = (k+1)<<1
while c < n and d[c := c+2 if d[c+2] < d[c] else c] < v: d[k], k, c = d[c], c, (c+1)<<1
if c < n+2 and d[c] < v: d[k], k = d[c], c
d[k] = v
if k+1 < n+2 and d[k+1] < d[k]:
d[k] = d[k+1]; k ^= 1
while rt <= (p := (k>>1)-1|1) and d[p] < v: d[k], k = d[p], p
d[k] = v
def reserve(A: list, est_len: int) -> None: ...
try:
from __pypy__ import resizelist_hint
except:
def resizelist_hint(A: list, est_len: int):
pass
reserve = resizelist_hint
from os import read as os_read, write as os_write, fstat as os_fstat
import sys
from __pypy__.builders import StringBuilder
def max2(a, b): return a if a > b else b
class IOBase:
@property
def char(io) -> bool: ...
@property
def writable(io) -> bool: ...
def __next__(io) -> str: ...
def write(io, s: str) -> None: ...
def readline(io) -> str: ...
def readtoken(io) -> str: ...
def readtokens(io) -> list[str]: ...
def readints(io) -> list[int]: ...
def readdigits(io) -> list[int]: ...
def readnums(io) -> list[int]: ...
def readchar(io) -> str: ...
def readchars(io) -> str: ...
def readinto(io, lst: list[str]) -> list[str]: ...
def readcharsinto(io, lst: list[str]) -> list[str]: ...
def readtokensinto(io, lst: list[str]) -> list[str]: ...
def readintsinto(io, lst: list[int]) -> list[int]: ...
def readdigitsinto(io, lst: list[int]) -> list[int]: ...
def readnumsinto(io, lst: list[int]) -> list[int]: ...
def wait(io): ...
def flush(io) -> None: ...
def line(io) -> list[str]: ...
class IO(IOBase):
BUFSIZE = 1 << 16; stdin: 'IO'; stdout: 'IO'
__slots__ = 'f', 'file', 'B', 'O', 'V', 'S', 'l', 'p', 'char', 'sz', 'st', 'ist', 'writable', 'encoding', 'errors'
def __init__(io, file):
io.file = file
try: io.f = file.fileno(); io.sz, io.writable = max2(io.BUFSIZE, os_fstat(io.f).st_size), ('x' in file.mode or 'r' not in file.mode)
except: io.f, io.sz, io.writable = -1, io.BUFSIZE, False
io.B, io.O, io.S = bytearray(), [], StringBuilder(); io.V = memoryview(io.B); io.l = io.p = 0
io.char, io.st, io.ist, io.encoding, io.errors = False, [], [], 'ascii', 'ignore'
def _dec(io, l, r): return io.V[l:r].tobytes().decode(io.encoding, io.errors)
def readbytes(io, sz): return os_read(io.f, sz)
def load(io):
while io.l >= len(io.O):
if not (b := io.readbytes(io.sz)):
if io.O[-1] < len(io.B): io.O.append(len(io.B))
break
pos = len(io.B); io.B.extend(b)
while ~(pos := io.B.find(b'\n', pos)): io.O.append(pos := pos+1)
def __next__(io):
if io.char: return io.readchar()
else: return io.readtoken()
def readchar(io):
io.load(); r = io.O[io.l]
c = chr(io.B[io.p])
if io.p >= r-1: io.p = r; io.l += 1
else: io.p += 1
return c
def write(io, s: str): io.S.append(s)
def readline(io): io.load(); l, io.p = io.p, io.O[io.l]; io.l += 1; return io._dec(l, io.p)
def readtoken(io):
io.load(); r = io.O[io.l]
if ~(p := io.B.find(b' ', io.p, r)): s = io._dec(io.p, p); io.p = p+1
else: s = io._dec(io.p, r-1); io.p = r; io.l += 1
return s
def readtokens(io): io.st.clear(); return io.readtokensinto(io.st)
def readints(io): io.ist.clear(); return io.readintsinto(io.ist)
def readdigits(io): io.ist.clear(); return io.readdigitsinto(io.ist)
def readnums(io): io.ist.clear(); return io.readnumsinto(io.ist)
def readchars(io): io.load(); l, io.p = io.p, io.O[io.l]; io.l += 1; return io._dec(l, io.p-1)
def readinto(io, lst):
if io.char: return io.readcharsinto(lst)
else: return io.readtokensinto(lst)
def readcharsinto(io, lst): lst.extend(io.readchars()); return lst
def readtokensinto(io, lst):
io.load(); r = io.O[io.l]
while ~(p := io.B.find(b' ', io.p, r)): lst.append(io._dec(io.p, p)); io.p = p+1
lst.append(io._dec(io.p, r-1)); io.p = r; io.l += 1; return lst
def _readint(io, r):
while io.p < r and io.B[io.p] <= 32: io.p += 1
if io.p >= r: return None
minus = x = 0
if io.B[io.p] == 45: minus = 1; io.p += 1
while io.p < r and io.B[io.p] >= 48: x = x * 10 + (io.B[io.p] & 15); io.p += 1
io.p += 1
return -x if minus else x
def readintsinto(io, lst):
io.load(); r = io.O[io.l]
while io.p < r and (x := io._readint(r)) is not None: lst.append(x)
io.l += 1; return lst
def _readdigit(io): d = io.B[io.p] & 15; io.p += 1; return d
def readdigitsinto(io, lst):
io.load(); r = io.O[io.l]
while io.p < r and io.B[io.p] > 32: lst.append(io._readdigit())
if io.B[io.p] == 10: io.l += 1
io.p += 1
return lst
def readnumsinto(io, lst):
if io.char: return io.readdigitsinto(lst)
else: return io.readintsinto(lst)
def line(io): io.st.clear(); return io.readinto(io.st)
def wait(io):
io.load(); r = io.O[io.l]
while io.p < r: yield
def flush(io):
if io.writable: os_write(io.f, io.S.build().encode(io.encoding, io.errors)); io.S = StringBuilder()
sys.stdin = IO.stdin = IO(sys.stdin); sys.stdout = IO.stdout = IO(sys.stdout)
def rd(): return IO.stdin.readints()
def rds(): return IO.stdin.__next__()
def rdl(n): return IO.stdin.readintsinto(elist(n))
def wt(s): IO.stdout.write(s)
def wtn(s): IO.stdout.write(f'{s}\n')
def wtnl(l): IO.stdout.write(' '.join(map(str, l)))
def elist(hint: int) -> list: ...
try:
from __pypy__ import newlist_hint
except:
def newlist_hint(hint): return []
elist = newlist_hint
if __name__ == '__main__':
main()