Problem p02610 (python)

Fixed submission:
import heapq
import sys
input = sys.stdin.readline


t = int(input())
for _ in range(t):
    n = int(input())
    info = [list(map(int, input().split())) for i in range(n)]
    p_li = []
    m_li = []
    ans = 0
    for k, l, r in info:
        diff = l - r
        if diff > 0:
            p_li.append((k - 1, abs(diff)))
            ans += r
        elif diff < 0:
            m_li.append((n - k - 1, abs(diff)))
            ans += l
        else:
            ans += l

    p_li = sorted(p_li, reverse=True)
    l = 0
    q = []
    for i in range(n)[::-1]:
        while l < len(p_li) and p_li[l][0] == i:
            heapq.heappush(q, -p_li[l][1])
            l += 1
        if q:
            val = -heapq.heappop(q)
            ans += val

    m_li = sorted(m_li, reverse=True)
    l = 0
    q = []
    for i in range(n)[::-1]:
        while l < len(m_li) and m_li[l][0] == i:
            heapq.heappush(q, -m_li[l][1])
            l += 1
        if q:
            val = -heapq.heappop(q)
            ans += val
    print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from random import random


class TreapNode:
    """Treapのノード定義
    メンバ変数: 値、優先度、親へのポインタ、左右の子へのポインタ"""
    def __init__(self, val):
        self.val = val
        self.priority = random()
        self.parent, self.right, self.left = None, None, None


class Treap:
    """平衡二分探索木: 値の検索、挿入、削除などクエリ処理をO(logN)で実行する"""
    def __init__(self, is_multiset=False):
        self.is_multiset = is_multiset
        self.root = None

    def search(self, val: int) -> bool:
        """値の検索: 集合に値valを持つノードが存在するか"""
        ptr = self.root
        while ptr is not None:
            if val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                return True
        return False

    def insert(self, val: int) -> bool:
        """値の削除: 集合に値valを持つノードを挿入する"""
        if self.root is None:
            self.root = TreapNode(val)
            return True

        # ノードの挿入
        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    ptr.left = TreapNode(val)
                    ptr.left.parent = ptr
                    ptr = ptr.left
                    break
                ptr = ptr.left
            else:
                if val == ptr.val and not self.is_multiset:
                    return False
                elif ptr.right is None:
                    ptr.right = TreapNode(val)
                    ptr.right.parent = ptr
                    ptr = ptr.right
                    break
                ptr = ptr.right

        # 木の回転によってヒープ性を保つ
        while (ptr.parent is not None) and (ptr.parent.priority > ptr.priority):
            if ptr.parent.right == ptr:
                self._rotate_left(ptr.parent)
            else:
                self._rotate_right(ptr.parent)
        if ptr.parent is None:
            self.root = ptr 
        return True

    def delete(self, val: int) -> True:
        """値の削除: 集合から値valを持つノードを削除する"""
        if self.root is None:
            return False

        ptr = self.root         
        while True: 
            if ptr is None:
                return False
            elif val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                break

        # 木の回転によって削除したいノードを葉に持っていく
        while (ptr.left is not None) or (ptr.right is not None):
            if ptr.left is None:
                self._rotate_left(ptr)
            elif ptr.right is None:
                self._rotate_right(ptr)
            elif ptr.left.priority < ptr.right.priority:
                self._rotate_right(ptr)
            else:
                self._rotate_left(ptr)
            if self.root == ptr:
                self.root = ptr.parent

        # ノードの削除
        if ptr.left is None and ptr.right is None:
            if ptr == self.root:
                self.root = None
            elif ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None      
        return True

    def _rotate_left(self, ptr):
        """木の左回転を行う"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def _rotate_right(self, ptr):
        """木の右回転を行う"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def search_min(self):
        ptr = self.root
        ret = None
        while ptr is not None:
            ret = ptr.val
            ptr = ptr.left
        return ret

    def search_max(self):
        ptr = self.root
        ret = None
        while ptr is not None:
            ret = ptr.val
            ptr = ptr.right
        return ret

    def search_le(self, val: int):
        """val以下の最大の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val <= val:
                ret = ptr.val
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_lt(self, val: int):
        """valよりも小さいの最大の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val < val:
                ret = ptr.val
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_ge(self, val: int):
        """val以上の最小の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val >= val:
                ret = ptr.val
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret
      
    def search_gt(self, val: int):
        """valよりも大きい最小の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val > val:
                ret = ptr.val
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret


t = int(input())
for _ in range(t):
    n = int(input())
    info = [list(map(int, input().split())) for i in range(n)]
    li = []
    ans = 0
    p_cnt = 0
    m_cnt = 0
    for k, l, r in info:
        diff = l - r
        ans += r
        if diff > 0:
           p_cnt += 1
        if diff < 0:
           m_cnt += 1
        li.append((diff, k - 1))
        li = sorted(li, reverse=True)

    tp1 = Treap()
    tp2 = Treap()
    

    for i in range(p_cnt):
        tp1.insert(i)
    for i in range(n - m_cnt, n):
        tp2.insert(i)

    for diff, k in li:
        if diff > 0:
            ind = tp1.search_le(k)
            if ind <= k:
                tp1.delete(ind)
                ans += diff
        elif diff == 0:
            continue
        else:
            ind = tp2.search_gt(k)
            if ind is not None:
                tp2.delete(ind)
            else:
                ans += diff
    print(ans)