Envío 6361

Código

from functools import total_ordering

@total_ordering
class Node:
    def __init__(self, s, p):
        self.s = s
        self.p = -p

    def __lt__(self, other):
        if self.p < other.p:
            return True
        elif self.p > other.p:
            return False
        return self.s < other.s
    
    def __eq__(self, other):
        return self.s == other.s and self.p == other.p

    def __repr__(self):
        return f"{self.s}"

class Heap:
    def __init__(self, n):
        self.tree = [None for _ in range(n + 1)]
        self.n = 0 

    def right(self, i):
        return (i << 1) + 1

    def left(self, i):
        return (i << 1) + 2

    def parent(self, i):
        return i >> 1

    def __len__(self):
        return self.n

    def heapify_down(self, i):
        l = self.left(i)
        r = self.right(i)
        children = [c for c in [l, r] if c < self.n]
        if all(self.tree[i] < self.tree[c] for c in children):
            return     
        sm = min(children, key = lambda x: self.tree[x])
        self.tree[sm], self.tree[i] = self.tree[i], self.tree[sm]
        self.heapify_down(sm)

    def heapify_up(self, i):
        while i != 0:
            p = self.parent(i)
            #print(f"{i=} {p=}")
            if self.tree[p] <= self.tree[i]:
                break    
            self.tree[p], self.tree[i] = self.tree[i], self.tree[p]
            i = p

    def add(self, elem):
        i = self.n
        self.tree[i] = elem
        self.n += 1
        self.heapify_up(i)


    def pop(self): 
        self.n -= 1 
        res = self.tree[0]
        self.tree[self.n], self.tree[0] = self.tree[0], self.tree[self.n] 
        self.tree[self.n] = None
        self.heapify_down(0)
        return res 

    def peek(self):
        return self.tree[0]

h = Heap(1_000_000)
num_lines = int(input())
for _ in range(num_lines):
    line = input()
    if line[0] == "I":
        _, s, p = line.split(" ")
        n = Node(s, int(p))
        h.add(n)
    elif line[0] == "G":
        n = h.peek()
        print(n)
    else:
        h.pop()