Problem:


Score : 500 points

Problem Statement

We have N camels numbered 1,2,\ldots,N.
Snuke has decided to make them line up in a row.

The happiness of Camel i will be L_i if it is among the K_i frontmost camels, and R_i otherwise.

Snuke wants to maximize the total happiness of the camels. Find the maximum possible total happiness of the camel.

Solve this problem for each of the T test cases given.

Constraints

All values in input are integers.

1 \leq T \leq 10^5

1 \leq N \leq 2 \times 10^{5}

1 \leq K_i \leq N

1 \leq L_i, R_i \leq 10^9

The sum of values of N in each input file is at most 2 \times 10^5.

Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is given in the following format:

N
K_1 L_1 R_1
\vdots
K_N L_N R_N

Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Sample Input 1

3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34

Sample Output 1

25
221
1354

In the first test case, it is optimal to line up the camels in the order 2, 1.

Camel 1 is not the frontmost camel, so its happiness will be 10.

Camel 2 is among the two frontmost camels, so its happiness will be 15.

In the second test case, it is optimal to line up the camels in the order 2, 1, 3.

Camel 1 is among the two frontmost camels, so its happiness will be 93.

Camel 2 is the frontmost camel, so its happiness will be 71.

Camel 3 is among the three frontmost camels, so its happiness will be 57.



Sample input:
3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34


Sample output:
25
221
1354

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop, heappush, heappushpop
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

T = int(readline())
sum = [0] * T
for i in range(T):
    N = int(readline())
    l1 = []
    l2 = []
    for j in range(N):
        a = list(map(int, readline().split()))
        if a[1] > a[2]:
            l1.append((-a[0], abs(a[1] - a[2])))
            sum[i] += a[2]
        else:
            if a[0] != N:
                l2.append((a[0], abs(a[2] - a[1])))
            sum[i] += a[1]
    sl1 = sorted(l1)
    sl2 = sorted(l2)
    h1 = []
    h2 = []
    poped = 0
    for j in range(1, N + 1):
        while len(sl1) > 0 and j == -sl1[-1][0]:
            l = sl1.pop()
            heappush(h1, -l[1])
        while poped <= j and len(h1) > 0:
            sum[i] += -heappop(h1)
            poped += 1
    poped = 0
    for j in reversed(range(1, N)):
        while len(sl2) > 0 and j == sl2[-1][0]:
            l = sl2.pop()
            heappush(h2, -l[1])
        while poped <= N - j and len(h2) > 0:
            sum[i] += -heappop(h2)
            poped += 1

for i in range(T):
    print(sum[i])

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        # 左右独立に解いて問題ない
        left = []
        right = []
        for i in range(N):
            k, l, r = map(int, input().split())
            if l > r: left.append((k, l, r))
            else: right.append((k, l, r))
            left.sort(key=lambda x: (x[0], -x[1]))
            right.sort(key=lambda x: (-x[0], -x[2]))
        ll = len(left)
        rl = len(right)
        #print("left={}".format(left))
        #print("right={}".format(right))

        ans = 0
        # 左側
        idx = 0
        S = 0
        while idx < ll:
            k = left[idx][0]
            while idx < ll and left[idx][0] == k:
                _, l, r = left[idx]
                if S < k:
                    ans += l
                    S += 1
                else:
                    ans += r
                idx += 1
        #print("left_val={}".format(ans))
        # 右側
        idx = 0
        S = N + 1
        while idx < rl:
            k = right[idx][0]
            while idx < rl and right[idx][0] == k:
                _, l, r = right[idx]
                if S > k + 1:
                    ans += r
                    S -= 1
                else:
                    ans += l
                idx += 1

        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush, heappushpop

T = int(input())
for i in range(T):
    N = int(input())
    sum = 0
    l1 = []
    l2 = []
    for j in range(N):
        a = list(map(int, input().split()))
        if a[1] > a[2]:
            l1.append((-a[0], abs(a[1] - a[2])))
            sum += a[2]
        else:
            if a[0] != N:
                l2.append((a[0], abs(a[2] - a[1])))
            sum += a[1]
    sl1 = sorted(l1)
    sl2 = sorted(l2)
    h1 = []
    h2 = []
    poped = 0
    for j in range(1, N + 1):
        while len(sl1) > 0 and j == -sl1[-1][0]:
            l = sl1.pop()
            heappush(h1, -l[1])
        while poped <= j and len(h1) > 0:
            sum += -heappop(h1)
            poped += 1
    poped = 0
    for j in reversed(range(1, N)):
        while len(sl2) > 0 and j == sl2[-1][0]:
            l = sl2.pop()
            heappush(h2, -l[1])
        while poped <= N - j and len(h2) > 0:
            sum += -heappop(h2)
            poped += 1

    print(sum)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        # 左右独立に解いて問題ない
        left = []
        right = []
        for i in range(N):
            k, l, r = map(int, input().split())
            if l > r: left.append((k, l, r))
            else: right.append((k, l, r))
            left.sort(key=lambda x: (x[0], -x[1]))
            right.sort(key=lambda x: (-x[0], -x[2]))
        ll = len(left)
        rl = len(right)
        #print("left={}".format(left))
        #print("right={}".format(right))

        ans = 0
        # 左側
        idx = 0
        S = 0
        while idx < ll:
            k = left[idx][0]
            while idx < ll and left[idx][0] == k:
                _, l, r = left[idx]
                if S <= k:
                    ans += l
                    S += 1
                else:
                    ans += r
                idx += 1
        #print("left_val={}".format(ans))
        # 右側
        idx = 0
        S = N
        while idx < rl:
            k = right[idx][0]
            while idx < rl and right[idx][0] == k:
                _, l, r = right[idx]
                if S > k:
                    ans += r
                    S -= 1
                else:
                    ans += l
                idx += 1

        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush, heappushpop

T = int(input())
for i in range(T):
    N = int(input())
    sum = 0
    l1 = []
    l2 = []
    for j in range(N):
        a = list(map(int, input().split()))
        if a[1] > a[2]:
            l1.append((-a[0], abs(a[1] - a[2])))
            sum += a[2]
        else:
            if a[0] != N:
                l2.append((a[0], abs(a[2] - a[1])))
            sum += a[1]
    sl1 = sorted(l1)
    sl2 = sorted(l2)
    h1 = []
    h2 = []
    poped = 0
    for j in range(1, N + 1):
        while len(sl1) > 0 and j == -sl1[-1][0]:
            l = sl1.pop()
            heappush(h1, l[1])
        while poped <= j and len(h1) > 0:
            sum += heappop(h1)
            poped += 1
    poped = 0
    for j in reversed(range(1, N)):
        while len(sl2) > 0 and j == sl2[-1][0]:
            l = sl2.pop()
            heappush(h2, l[1])
        while poped <= N - j and len(h2) > 0:
            sum += heappop(h2)
            poped += 1

    print(sum)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

t = int(input())
for i in range(t):
  n = int(input())
  klr = [list(map(int, input().split())) for i in range(n)]
  plus = []
  p_que = []
  minus = []
  m_que = []
  ans = 0
  for key, (k,l,r) in enumerate(klr):
    diff = l-r
    if diff >= 0:
      plus.append([k, diff, key])
      heappush(p_que,(diff, k, key))
      ans += r
    else:
      minus.append([k, -diff, key])
      heappush(m_que,(-diff, k, key))
      ans += l
  plus.sort(reverse=True)
  used = [0] * n
  now = len(plus)
  for k,diff,key in plus:
    while now > k:
      data = heappop(p_que)
      idx = data[2]
      if used[idx]:
        continue
      used[idx] = 1
      now -= 1
    if used[key]:
      continue
    used[key] = 1
    ans += diff
    now -= 1
  now = len(plus) + 1      
  minus.sort()
  for k,diff,key in minus:
    while now <= k:
      data = heappop(m_que)
      idx = data[2]
      if used[idx]:
        continue
      used[idx] = 1
      now += 1
    if used[key]:
      continue
    used[key] = 1
    ans += diff
    now += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush, heappushpop

T = int(input())
for i in range(T):
    N = int(input())
    sum = 0
    l1 = []
    l2 = []
    for j in range(N):
        a = list(map(int, input().split()))
        if a[1] > a[2]:
            l1.append((-a[0], abs(a[1] - a[2])))
            sum += a[2]
        else:
            if a[0] != N:
                l2.append((a[0], abs(a[2] - a[1])))
            sum += a[1]
    sl1 = sorted(l1)
    sl2 = sorted(l2)
    h1 = []
    h2 = []
    poped = 0
    for j in range(1, N + 1):
        while len(sl1) > 0 and j == -sl1[-1][0]:
            l = sl1.pop()
            heappush(h1, l[1])
        while poped <= j and len(h1) > 0:
            sum += heappop(h1)
            poped += 1
    poped = 0
    for j in reversed(range(1, N)):
        while len(sl2) > 0 and j == sl2[-1][0]:
            l = sl2.pop()
            heappush(h2, l[1])
        while poped < N - j and len(h2) > 0:
            sum += heappop(h2)
            poped += 1

    print(sum)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>=r:x+=[[k,l,r]]
  else:y+=[[n-k,r,l]]
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   if k>0:s+=l;heappush(h,l-r)
   else:s+=r
   if len(h)>k:s+=heappop(h)
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>=r:x+=[[k,l,r]]
  else:y+=[[n-k,r,l]]
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   if k:s+=l;heappush(h,l-r)
   else:s+=r
   if len(h)>k:s+=heappop(h)
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>=r:s+=r;x+=[[n,r-l]]
  else:s+=l;y+=[[n-k,l-r]]*(k<n)
 for x in x,y:
  x.sort();h=[]
  for k,d in x:
   heappush(h,-d)
   if len(h)>k:heappop(h)
  for d in h:s+=d
 print(s)

Submission status: Wrong Answer

Solution code:
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();m=len(x);h=[(0,0)]*n
  while h:
   while[[m]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   s+=heappop(h)[~(m>0)];m-=1
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>=r:s+=r;x+=[[n,l-r]]
  else:s+=l;y+=[[n-k,r-l]]*(k<n)
 for x in x,y:
  x.sort();h=[]
  for k,d in x:
   heappush(h,d)
   if len(h)>k:heappop(h)
  for d in h:s+=d
 print(s)

Submission status: Wrong Answer

Solution code:
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();n=len(x);h=[(0,0)]*n
  while h:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   s+=heappop(h)[~(n>0)];n-=1
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>=r:s+=r;x+=[[n,r-l]]
  else:s+=l;y+=[[n-k,l-r]]*(k<n)
 for x in x,y:
  x.sort();h=[]
  for k,d in x:
   heappush(h,d)
   if len(h)>k:heappop(h)
  for d in h:s-=d
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=t=[*map(int,i().split())]
  if l>=r:s+=r;x+=[t]
  else:s+=l;y+=[[n-k,r,l]]*(k<n)
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   heappush(h,r-l)
   if len(h)>k:heappop(h)
  for d in h:s-=d
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>=r);y+=[[n-k,r,l]]*(l<r)
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   assert l>=r
   if k>0:s+=l;heappush(h,r-l)
   else:s+=r
   if len(h)>k:s+=heappop(h)
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>=r);y+=[[n-k,r,l]]*(l<r)
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   if k>0:s+=l;heappush(h,r-l)
   else:s+=r
   if len(h)>k:s+=heappop(h)
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   if k>0:s+=l;heappush(h,r-l)
   else:s+=r
   if len(h)>k:s+=heappop(h)
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   if k<n:heappush(h,(r-l,l,r))
   if len(h)>k:s+=heappop(h)[0]
   s+=l
 print(s)

Submission status: Wrong Answer

Solution code:
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   heappush(h,(r-l,l,r))
   if len(h)>k:s+=heappop(h)[2]
  for k,l,r in h:s+=l
 print(s)

Submission status: Wrong Answer

Solution code:


# 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, True))
				train[i] = (L, R)
				score += L
			else:
				score += R
		else:
			score += R
#	print(train)
	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))

Submission status: Wrong Answer

Solution code:
import heapq
for _ in range(int(input())):
    N=int(input())
    ListL=[]
    ListR=[]
    ans=0
    for _ in range(N):
        k,l,r=map(int,input().split())
        ans+=min(l,r)
        if l>=r:
            ListL.append([k-1,abs(l-r)])
        else:
            ListR.append([N-k,abs(l-r)])
    S=[]
    for i in range(N):
        for j in range(len(ListL)):
            if ListL[j][0]==i:
                heapq.heappush(S,ListL[j][1])
        while len(S)>i+1:
            heapq.heappop(S) 
    ans+=sum(S)
    S=[]
    for i in range(1,N):
        for j in range(len(ListR)):
            if ListR[j][0]==i:
                heapq.heappush(S,ListR[j][1])
        while len(S)>i+1:
            heapq.heappop(S) 
    ans+=sum(S)

    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

t = int(input())
for i in range(t):
  n = int(input())
  klr = [list(map(int, input().split())) for i in range(n)]
  plus = []
  p_que = []
  minus = []
  m_que = []
  ans = 0
  for key, (k,l,r) in enumerate(klr):
    diff = l-r
    if diff >= 0:
      plus.append([k, diff, key])
      heappush(p_que,(diff, k, key))
      ans += r
    else:
      minus.append([k, -diff, key])
      heappush(m_que,(-diff, k, key))
      ans += l
  plus.sort(reverse=True)
  used = [0] * n
  now = len(plus)
  for k,diff,key in plus:
    while now > k:
      data = heappop(p_que)
      idx = data[2]
      if used[idx]:
        continue
      used[idx] = 1
      now -= 1
    if used[key]:
      continue
    used[key] = 1
    ans += diff
    now -= 1
  assert now == 0
  now = len(plus) + 1      
  minus.sort()
  for k,diff,key in minus:
    while now <= k:
      data = heappop(m_que)
      idx = data[2]
      if used[idx]:
        continue
      used[idx] = 1
      now += 1
    if used[key]:
      continue
    used[key] = 1
    ans += diff
    now += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[(n-k,r,l)]*(l<r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)

Submission status: Wrong Answer

Solution code:
from heapq import*
i=input
h=heappush
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];h(x,t)if l>r else h(y,(n-k,r,l))
 for x in x,y:
  n,*q=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:_,l,r=x.pop();h(q,(r-l,l,r))
   if q:s+=heappop(q)[1]
  for*_,r in x+q:s+=r
 print(s)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
Q = I()


for _ in range(Q):
  N = I()
  data = ILL(N)
  Mdata = []
  Udata = []
  for K,L,R in data:
    if L>=R:
      Mdata.append([K,L,R])
    else:
      Udata.append([K,L,R])
  Mdata.sort(key=lambda x:-abs(x[1]-x[2]))
  Udata.sort(key=lambda x:-abs(x[1]-x[2]))
  ans = 0
  Mlen = len(Mdata)
  Ulen = len(Udata)
  MAE = [i for i in range(Mlen)]
  def CANSIT_MAE(x):
    x = min(x,Mlen-1)
    if MAE[x] == -1:
      return -1
    elif MAE[x] == x:
      MAE[x] = x-1
      return x
    else:
      MAE[x] = CANSIT_MAE(MAE[x])
      return MAE[x]
  USHIRO = [i for i in range(Ulen)]
  def CANSIT_USHIRO(x):
    x = min(x,Ulen-1)
    if USHIRO[x] == -1:
      return -1
    elif USHIRO[x] == x:
      USHIRO[x] = x-1
      return x
    else:
      USHIRO[x] = CANSIT_USHIRO(USHIRO[x])
      return USHIRO[x]
  for K,L,R in Mdata:
    if L==R or K==N:
      ans += L
    else:
      if CANSIT_MAE(K)!=-1:
        ans += L
      else:
        ans += R
  for K,L,R in Udata:
    if L==R or K==N:
      ans += L
    else:
      if CANSIT_USHIRO(N-1-K)!=-1:
        ans += R
      else:
        ans += L
  print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

# from collections import defaultdict
from heapq import heappush, heappop
# import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solveOLD(N, XS):
    XS.sort()
    table = [0]
    for i in range(N):
        newtable = [0] * (i + 2)
        K, L, R = XS[i]
        for j in range(i + 1):
            if j < K:
                newtable[j + 1] = table[j] + L
            v = table[j] + R
            if v > newtable[j]:
                newtable[j] = v
        table = newtable
        debug(": table", table)
    return max(table)


def solveNG(N, XS):
    XS.sort()
    table = [0, 0]
    cursor = [0, 0]
    j = 0
    for i in range(N):
        newtable = [0] * 2
        K, L, R = XS[i]

        if cursor[1] < K:
            newtable[1] = table[1] + L
            cursor[1] += 1
        newtable[0] = table[1] + R
        if v > newtable[j]:
            newtable[j] = v
        table = newtable
        debug(": table", table)
    return max(table)


def solve(N, XS):
    head = []
    tail = []
    for i in range(N):
        K, L, R = XS[i]
        if L > R:
            heappush(head, (K, L, R))
        else:
            heappush(tail, (N - K, R, L))

    ret = 0
    selected = []
    for i in range(len(head)):
        K, L, R = heappop(head)
        heappush(selected, (L - R, K, L, R))
        ret += L
        if K <= i:
            worst = heappop(selected)
            ret -= worst[0]

    selected = []
    for i in range(len(tail)):
        K, L, R = heappop(tail)
        heappush(selected, (L - R, K, L, R))
        ret += L
        if K <= i:  # ?
            worst = heappop(selected)
            ret -= worst[0]

    return ret


def main():
    # parse input
    T = int(input())
    for i in range(T):
        N = int(input())
        XS = []
        for j in range(N):
            XS.append(tuple(map(int, input().split())))
        print(solve(N, XS))


# tests
T1 = """
3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    25
    221
    1354
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


t = int(input())
ANS = [None]*t
from collections import defaultdict
from heapq import heappop as hpp, heappush as hp
for iii in range(t):
    n = int(input())
    lr = [None]*n
    # d1 = defaultdict(list)
    # d0 = defaultdict(list)
    for i in range(n):
        k,l,r = list(map(int, input().split()))
        lr[i] = (l - r, k, l, r, i)
        # if l-r>=0:
        #     d1[k].append((-l+r, l, r, i))
        # else:
        #     d0[k].append((l-r, l, r, i))
            
    lr1 = [item for item in lr if item[0]>=0]
    lr0 = [item for item in lr if item[0]<0]
    lr1.sort(reverse=True)
    lr0.sort()

    bit1 = [0]*(n+1)
    bit0 = [0]*(n+1)
    sl = set()
    sr = set()
    h = []
    for val, k, l, r, i in lr1:
        if k==n:
            sl.add(i)
        elif query(bit1, k)<k:
            sl.add(i)
            add(bit1, k, 1)
        else:
            sr.add(i)
    total = 0
    for val, k, l, r, i in lr0:
        if k==n:
            sl.add(i)
        else:
            if total-query(bit0, k)<(n-k):
                sr.add(i)
                add(bit0, k+1, 1)
                total += 1
            else:
                sl.add(i)
    ans = 0
#     print(lr0, lr1, sl, sr)
    assert len(sl) + len(sr) == n
    for i in sl:
        ans += lr[i][-3]
    for i in sr:
        ans += lr[i][-2]
    ANS[iii] = ans
write("\n".join(map(str, ANS)))