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_2heaps_fast_heapq.test.py

Depends on

Code

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/double_ended_priority_queue
# modified from abUma: https://judge.yosupo.jp/submission/144329
from cp_library.ds.reserve_fn import reserve
from cp_library.ds.heap.fast_heapq import heappop, heappush, heapify

class DoubleEndedPriorityQueue:
    def __init__(self, n: int, q: int, arr: list[int]=None) -> None:
        self.hq1 = arr
        self.hq2 = [0]*n
        reserve(self.hq1, n+q)
        reserve(self.hq2, n+q)
        self.used = bytearray(n+q)
        if arr:
            for i, x in enumerate(S):
                self.hq1[i] = tmp = x << 28 | i
                self.hq2[i] = ~tmp
        heapify(self.hq1)
        heapify(self.hq2)
    
    def pop_min(self):
        while 1:
            tmp = heappop(self.hq1)
            x, i = tmp >> 28, tmp & 0xfffffff
            if self.used[i]: continue
            self.used[i] = 1
            return x
        
    def pop_max(self):
        while 1:
            tmp = ~heappop(self.hq2)
            x, i = tmp >> 28, tmp & 0xfffffff
            if self.used[i]: continue
            self.used[i] = 1
            return x
        
    def push(self, x: int, i: int) -> None:
        heappush(self.hq1, tmp := x << 28 | i)
        heappush(self.hq2, ~tmp)

from cp_library.io.fast.fast_io_fn import rd, rdl, wtn

N, Q = rd(), rd()
S = rdl(N)
depq = DoubleEndedPriorityQueue(N, Q, S)
for i in range(Q):
    cmd = rd()
    if cmd == 0:
        x = rd()
        depq.push(x, i + N)
    elif cmd == 1:
        wtn(depq.pop_min())
    else:
        wtn(depq.pop_max())
# verification-helper: PROBLEM https://judge.yosupo.jp/problem/double_ended_priority_queue
# modified from abUma: https://judge.yosupo.jp/submission/144329
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

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


def heappush(heap: list, item):
    heap.append(item)
    heapsiftdown(heap, 0, len(heap)-1)

def heappop(heap: list):
    item = heap.pop()
    if heap: item, heap[0] = heap[0], item; heapsiftup(heap, 0)
    return item

def heapreplace(heap: list, item):
    item, heap[0] = heap[0], item; heapsiftup(heap, 0)
    return item

def heappushpop(heap: list, item):
    if heap and heap[0] < item: item, heap[0] = heap[0], item; heapsiftup(heap, 0)
    return item

def heapify(x: list):
    for i in reversed(range(len(x)//2)): heapsiftup(x, i)

def heapsiftdown(heap: list, root: int, pos: int):
    item = heap[pos]
    while root < pos and item < heap[p := (pos-1)>>1]: heap[pos], pos = heap[p], p
    heap[pos] = item

def heapsiftup(heap: list, pos: int):
    n, item, c = len(heap)-1, heap[pos], pos<<1|1
    while c < n and heap[c := c+(heap[c+1]<heap[c])] < item: heap[pos], pos, c = heap[c], c, c<<1|1
    if c == n and heap[c] < item: heap[pos], pos = heap[c], c
    heap[pos] = item

def heappop_max(heap: list):
    item = heap.pop()
    if heap: item, heap[0] = heap[0], item; heapsiftup_max(heap, 0)
    return item

def heapreplace_max(heap: list, item):
    item, heap[0] = heap[0], item; heapsiftup_max(heap, 0)
    return item

def heapify_max(x: list):
    for i in reversed(range(len(x)//2)): heapsiftup_max(x, i)

def heappush_max(heap: list, item):
    heap.append(item); heapsiftdown_max(heap, 0, len(heap)-1)

def heapreplace_max(heap: list, item):
    item, heap[0] = heap[0], item; heapsiftup_max(heap, 0)
    return item

def heappushpop_max(heap: list, item):
    if heap and heap[0] > item: item, heap[0] = heap[0], item; heapsiftup_max(heap, 0)
    return item

def heapsiftdown_max(heap: list, root: int, pos: int):
    item = heap[pos]
    while root < pos and heap[p := (pos-1)>>1] < item: heap[pos], pos = heap[p], p
    heap[pos] = item

def heapsiftup_max(heap: list, pos: int):
    n, item, c = len(heap)-1, heap[pos], pos<<1|1
    while c < n and item < heap[c := c+(heap[c]<heap[c+1])]: heap[pos], pos, c = heap[c], c, c<<1|1
    if c == n and item < heap[c]: heap[pos], pos = heap[c], c
    heap[pos] = item

# def heapsiftdown(heap: list, root: int, pos: int):
#     item = heap[pos]
#     while root < pos and item < heap[p := (pos-1)>>1]: heap[pos], pos = heap[p], p
#     heap[pos] = item

# def heapsiftup(heap: list, pos: int):
#     n, item, c = len(heap)-1, heap[pos], pos<<1|1
#     while c < n and heap[c := c+(heap[c+1]<heap[c])] < item: heap[pos], pos, c = heap[c], c, c<<1|1
#     if c == n and heap[c] < item: heap[pos], pos = heap[c], c
#     heap[pos] = item

class DoubleEndedPriorityQueue:
    def __init__(self, n: int, q: int, arr: list[int]=None) -> None:
        self.hq1 = arr
        self.hq2 = [0]*n
        reserve(self.hq1, n+q)
        reserve(self.hq2, n+q)
        self.used = bytearray(n+q)
        if arr:
            for i, x in enumerate(S):
                self.hq1[i] = tmp = x << 28 | i
                self.hq2[i] = ~tmp
        heapify(self.hq1)
        heapify(self.hq2)
    
    def pop_min(self):
        while 1:
            tmp = heappop(self.hq1)
            x, i = tmp >> 28, tmp & 0xfffffff
            if self.used[i]: continue
            self.used[i] = 1
            return x
        
    def pop_max(self):
        while 1:
            tmp = ~heappop(self.hq2)
            x, i = tmp >> 28, tmp & 0xfffffff
            if self.used[i]: continue
            self.used[i] = 1
            return x
        
    def push(self, x: int, i: int) -> None:
        heappush(self.hq1, tmp := x << 28 | i)
        heappush(self.hq2, ~tmp)



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)))

N, Q = rd(), rd()
S = rdl(N)
depq = DoubleEndedPriorityQueue(N, Q, S)
for i in range(Q):
    cmd = rd()
    if cmd == 0:
        x = rd()
        depq.push(x, i + N)
    elif cmd == 1:
        wtn(depq.pop_min())
    else:
        wtn(depq.pop_max())
Back to top page