cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: test/library-checker/data-structure/double_ended_priority_queue.test.py

Depends on

Code

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/double_ended_priority_queue

def main():
    N, Q = rd(), rd()
    S = rdl(N)
    reserve(S, N+Q)
    heap = IntervalHeap(S)

    for _ in range(Q):
        t = rd()
        if t == 0: heap.push(rd())
        elif t == 1: wtn(heap.pop_min())
        else: wtn(heap.pop_max())

from cp_library.ds.heap.interval_heap_cls import IntervalHeap
from cp_library.ds.reserve_fn import reserve
from cp_library.io.fast.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(), rd()
    S = rdl(N)
    reserve(S, N+Q)
    heap = IntervalHeap(S)

    for _ in range(Q):
        t = rd()
        if t == 0: heap.push(rd())
        elif t == 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 __pypy__.builders import StringBuilder
import sys
from os import read as os_read, write as os_write
from atexit import register as atexist_register

class Fastio:
    ibuf = bytes()
    pil = pir = 0
    sb = StringBuilder()
    def load(self):
        self.ibuf = self.ibuf[self.pil:]
        self.ibuf += os_read(0, 131072)
        self.pil = 0; self.pir = len(self.ibuf)
    def flush_atexit(self): os_write(1, self.sb.build().encode())
    def flush(self):
        os_write(1, self.sb.build().encode())
        self.sb = StringBuilder()
    def fastin(self):
        if self.pir - self.pil < 64: self.load()
        minus = x = 0
        while self.ibuf[self.pil] < 45: self.pil += 1
        if self.ibuf[self.pil] == 45: minus = 1; self.pil += 1
        while self.ibuf[self.pil] >= 48:
            x = x * 10 + (self.ibuf[self.pil] & 15)
            self.pil += 1
        if minus: return -x
        return x
    def fastin_string(self):
        if self.pir - self.pil < 64: self.load()
        while self.ibuf[self.pil] <= 32: self.pil += 1
        res = bytearray()
        while self.ibuf[self.pil] > 32:
            if self.pir - self.pil < 64: self.load()
            res.append(self.ibuf[self.pil])
            self.pil += 1
        return res
    def fastout(self, x): self.sb.append(str(x))
    def fastoutln(self, x): self.sb.append(str(x)); self.sb.append('\n')
fastio = Fastio()
rd = fastio.fastin; rds = fastio.fastin_string; wt = fastio.fastout; wtn = fastio.fastoutln; flush = fastio.flush
atexist_register(fastio.flush_atexit)
sys.stdin = None; sys.stdout = None
def rdl(n):
    lst = [0]*n
    for i in range(n): lst[i] = rd()
    return lst
def wtnl(l): wtn(' '.join(map(str, l)))

if __name__ == '__main__':
    main()
Back to top page