Buggy python submission (verdict: Time Limit Exceeded):


# point update
# range query
class SegmentTreeNode:
	def __init__(self, start, end, initial, merge):
#		print("s", start, end)
		self.start = start
		self.end = end
		self.width = end - start
		self.merge = merge
		self.initial = initial
		if self.width > 1:
			w2 = self.width // 2
			self.left = SegmentTreeNode(start, start + w2, initial, merge)
			self.right = SegmentTreeNode(start + w2, end, initial, merge)
			self.value = self.merge(self.left.value, self.right.value)
		else:
			self.value = self.initial

	def update(self, index, value):
		if self.start <= index and index < self.end:
			if self.width == 1:
				self.value = value
			else:
				self.left.update(index, value)
				self.right.update(index, value)
				self.value = self.merge(self.left.value, self.right.value)
	
	def pick(self, start, end):
		if start <= self.start and self.end <= end:
			return self.value
		elif self.start < end and self.end > start:
#			m = self.merge(self.left.pick(start, end), self.right.pick(start, end))
#			print(start, end, m)
			return self.merge(self.left.pick(start, end), self.right.pick(start, end))
		else:
			return self.initial
	
	def to_list(self, items):
		if self.width == 1:
			items.append(self.value)
		else:
			self.left.to_list(items)
			self.right.to_list(items)
	
class SegmentTree:
	def __init__(self, n, *, merge, initial = None):
		width = 1
		while width < n:
			width *= 2
		self.root = SegmentTreeNode(0, width, initial, merge)
		self.root.value = 0
		self.capacity = width
	
	def update(self, index, value):
		self.root.update(index, value)
	
	def pick(self, start, end):
		return self.root.pick(start, end)
	
	def to_list(self):
		items = []
		self.root.to_list(items)
		return items
	

def merge(l, r):
	if r[1]:
		return r
	else:
		return l

import sys

T = int(input())

def calc(camels):
	camels.sort()
	count = len(camels)
	st = SegmentTree(count, merge = merge, initial = (None, False))
	for i in range(count):
		st.update(i, (i, True))
	for i in range(count + 1, st.capacity):
		st.update(i, (i, False))
	score = 0
	train = [None] * N
	for D, L, R, K in camels:
		if K >= 0:
			i, c = st.pick(0, min(K, count))
#			print(st.to_list(), file = sys.stderr)
#			print(L, R, K, i, c, file = sys.stderr)
			if c:
#				print("x", i, L, R, file = sys.stderr)
				st.update(i, (i, False))
				train[i] = (L, R)
				score += L
			else:
				score += R
		else:
			score += R
#	print(train, file = sys.stderr)
	return score

for t in range(T):
#	print(f"t = {t}", file = sys.stderr)
	N = int(input())
	
	camels_l = []
	camels_r = []
	
	count_r = 0
	for _ in range(N):
		K, L, R = map(int, input().split())
		D = L - R
		if D >= 0:
			camels_l.append((-D, L, R, K))
		else:
			camels_r.append((D, R, L, N - K))
	
#	print(camels_l)
#	print(camels_r)
	
	print(calc(camels_l) + calc(camels_r))


Fixed submission:
T = int(input())

import heapq

def calc(camels):
	camels.sort()
	camels.reverse()
	count = len(camels)
	
	score = 0
	queue = []
	i = 0
	for k in range(count, 0, -1):
		while i < count and camels[i][0] >= k:
			K, L, R = camels[i]
			heapq.heappush(queue, (-(L - R), L, R))
			i += 1
		if len(queue) > 0:
			D, L, R = heapq.heappop(queue)
			score += L
	while len(queue) > 0:
		D, L, R = heapq.heappop(queue)
		score += R
	while i < count:
		K, L, R = camels[i]
		score += R
		i += 1
	return score

for t in range(T):
	N = int(input())
	
	camels_l = []
	camels_r = []
	
	count_r = 0
	for _ in range(N):
		K, L, R = map(int, input().split())
		if L - R >= 0:
			camels_l.append((K, L, R))
		else:
			camels_r.append((N - K, R, L))
	
	print(calc(camels_l) + calc(camels_r))