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:
T = int(input())
for _ in range(T):
    N = int(input())
    KLR = [list(map(int, input().split())) for i in range(N)]
    ans = 0
    KLR.sort(key=lambda x: x[2])

    for i, klr in enumerate(KLR):
        K, L, R = klr
        if R >= L and N >= K:
            ans += R
            N -= 1
            KLR[i][2] = -1
    # print(ans, KLR)
    KLR = [(K, L, R) for K, L, R in KLR if R >= 0]
    KLR.sort(key=lambda x: x[0])
    l = 1
    for K, L, R in KLR:
        if K >= l:
            ans += L
            l += 1
        else:
            ans += R
            N -= 1
    print(ans)

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
  N = int(input())
  base = 0
  A = []
  B = [0 for _ in range(N)]
  C =[]
  for i in range(N):
    K, L, R = map(int,input().split()) 
    L -= min(L,R)
    R -= min(L,R)
    if L > R:
      A.append((L,K,0))
    if L > R:
      A.append((R,K,1))
    base += min(L,R)
  A.sort(reverse = True)
  
  l = 0
  r = N-1
  for a in A:
    if a[2] == 0:
      if l < K:
        l += 1
        base += L 
    else:
      if r >= K:
        r -= 1
        base += R
  print(base)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    T = NI()
    for z in range(T):

        N = NI()
        c = []

        N0 = 2 ** (N.bit_length())
        st0 = [0] * (2 * N0)
        st1 = [0] * (2 * N0)

        def update_max(i, x):
            i += N0 - 1
            st1[i] = max(st1[i], x)
            while i > 0:
                i = (i - 1) // 2
                st1[i] = max(st1[i * 2 + 1], st1[i * 2 + 2])

        def query_max(l, r):
            L = l + N0;
            R = r + N0
            ret = 0
            while L < R:
                if L % 2:
                    ret = max(ret, st1[L - 1])
                    L += 1
                if R % 2:
                    R -= 1
                    ret = max(ret, st1[R - 1])
                L //= 2;
                R //= 2
            return ret

        def update_min(i, x):
            i += N0 - 1
            st0[i] = min(st0[i], x)
            while i > 0:
                i = (i - 1) // 2
                st0[i] = min(st0[i * 2 + 1], st0[i * 2 + 2])

        def query_min(l, r):
            L = l + N0;
            R = r + N0
            ret = N + 1  # max value
            while L < R:
                if L % 2:
                    ret = min(ret, st0[L - 1])
                    L += 1
                if R % 2:
                    R -= 1
                    ret = min(ret, st0[R - 1])
                L //= 2;
                R //= 2
            return ret

        for i in range(1,N+1):
            update_min(i,i)
            update_max(i,i)

        for _ in range(N):
            k,l,r = LI()
            if l < r:
                c.append((r-l,r,l,-k))
            else:
                c.append((l-r,l,r,k))
        c.sort(reverse=True)
        ans = 0
        for sa,p1,p2,k in c:
            if k > 0:
                u = query_max(1,k+1)
                if u > 0:
                    ans += p1
                    update_max(u,0)
                else:
                    ans += p2
            else:
                u = query_min(abs(k)+1,N+1)
                if u < N+1:
                    ans += p1
                    update_min(u,N+1)
                else:
                    ans += p2
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq

class BinaryIndexedTree:
    # Initialize BIT with non-zero value
    def __init__(self, array):
        self.len = len(array)
        self.data = [0] + array
        self.build()

    def build(self):
        for i in range(1, self.len):
            if i + (i & -i) > self.len:
                continue
            self.data[i + (i & -i)] += self.data[i]

    # Add w to a[x] (0-indexed)
    def add(self, x, w):
        x += 1
        while x <= self.len:
            self.data[x] += w
            x += x & -x

    # Get Sum of a[0 : x) (0-indexed)
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.data[x]
            x -= x & -x
        return ret

    # Get first index s.t. sum a[0 : index) >= w
    def bisect_left(self, w):
        if w <= 0:
            return 0
        x = 0
        delta = pow(2, (self.len - 1).bit_length())
        while delta > 0:
            if x + delta <= self.len and self.data[x + delta] < w:
                w -= self.data[x + delta]
                x += delta
            delta >>= 1
        return x

t = int(input())
for _ in range(t):
    n = int(input())
    q = []
    base = 0
    left = BinaryIndexedTree([0] * n)
    right = BinaryIndexedTree([0] * n)
    left_bag = [[] for _ in range(n)]
    right_bag = [[] for _ in range(n)]
    for _ in range(n):
        k, l, r = map(int, input().split())
        if k == n:
            base += l
            continue
        if l == r:
            base += l
        elif l > r:
            q.append((l-r, 0, k-1))
            base += r
            left_bag[k-1].append(l-r)
        else:
            q.append((r-l, 1, n-k-1))
            base += l
            right_bag[n-k-1].append(r-l)
    
    left_bag.reverse()
    hq = []
    for bag in left_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, item)
        if hq:
            base += heapq.heappop(hq) 
    right_bag.reverse()
    hq = []
    for bag in right_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, item)
        if hq:
            base += heapq.heappop(hq) 
    print(base)

Submission status: Wrong Answer

Solution code:
t = int(input())
while t:
    t-=1
    n = int(input())
    klr = [list(map(int, input().split())) for i in range(n)]
    klr.sort(key=lambda x:(x[0],-x[1]))
    ans = 0
    l = 0
    r = 0
    for i in range(n):
        if(i>0 and klr[i][0] != klr[i-1][0]):
            inc = klr[i][0]-klr[i-1][0]
        if (klr[i][1]>=klr[i][2] and l<klr[i][0]) or r>=n-klr[i][0]:
            ans += klr[i][1]
            l += 1
        else:
            ans += klr[i][2]
            r += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
  n=int(input())
  s=0
  list1=[]
  list2=[]
  for i in range(n):
    k,l,r=map(int,input().split())
    s+=min(l,r)
    if l-r>0: list1.append((l-r,k))
    else: list2.append((r-l,k))

  list1=sorted(list1, reverse=True, key=lambda x: x[0])
  list2=sorted(list2, reverse=True, key=lambda x: x[0])

  dic={p:0 for p in range(1,n+1)}
  for x in list1:
    w=x[1]
    dic[w]+=1
    if dic[w]<=w: s+=x[0]

  dic={p:0 for p in range(1,n+1)}
  for x in list2:
    w=x[1]
    dic[w]+=1
    if dic[w]<=n-w: s+=x[0]
  print(s)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    T = Z()
    ans = []
    for _ in range(T):
        N = Z()
        camel1 = []
        camel2 = []
        for _ in range(N):
            k, l, r = ZZ()
            if l > r: camel1.append([k, -l, r])
            else: camel2.append([-k, -r, l])
        camel1.sort()
        camel2.sort()
        order = 1
        cc = 0
        for i in range(len(camel1)):
            k, l, r = camel1[i]
            l = -l
            if order <= k: cc += l
            else: cc += r
            order += 1
        order = N
        for i in range(len(camel2)):
            k, r, l = camel2[i]
            k = -k
            r = -r
            if order <= k: cc += l
            else: cc += r
            order -= 1

        ans.append(cc)

    for a in ans:
        print(a)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
t = int(input())
for i in range(t):
    n = int(input())
    klr = [[0] + list(map(int,input().split())) for i in range(n)]
    for i in range(n):
        if klr[i][2] < klr[i][3]:
            klr[i][0] = 1
    
    klr = sorted(klr, key=lambda x:(x[0], x[1]))
    
    cnt = 0
    for i in range(n):
        if i+1 <= klr[i][1]:
            cnt += klr[i][2]
        else:
            cnt += klr[i][3]
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    T = NI()
    for z in range(T):

        N = NI()
        c = []

        N0 = 2 ** (N.bit_length())
        st0 = [0] * (2 * N0)
        st1 = [0] * (2 * N0)

        def update_max(i, x):
            i += N0 - 1
            st1[i] = max(st1[i], x)
            while i > 0:
                i = (i - 1) // 2
                st1[i] = max(st1[i * 2 + 1], st1[i * 2 + 2])

        def query_max(l, r):
            L = l + N0;
            R = r + N0
            ret = 0
            while L < R:
                if L % 2:
                    ret = max(ret, st1[L - 1])
                    L += 1
                if R % 2:
                    R -= 1
                    ret = max(ret, st1[R - 1])
                L //= 2;
                R //= 2
            return ret

        def update_min(i, x):
            i += N0 - 1
            st0[i] = min(st0[i], x)
            while i > 0:
                i = (i - 1) // 2
                st0[i] = min(st0[i * 2 + 1], st0[i * 2 + 2])

        def query_min(l, r):
            L = l + N0;
            R = r + N0
            ret = N + 1  # max value
            while L < R:
                if L % 2:
                    ret = min(ret, st0[L - 1])
                    L += 1
                if R % 2:
                    R -= 1
                    ret = min(ret, st0[R - 1])
                L //= 2;
                R //= 2
            return ret

        for i in range(1,N+1):
            update_min(i,i)
            update_max(i,i)

        for _ in range(N):
            k,l,r = LI()
            if l < r:
                c.append((r-l,r,l,-k))
            else:
                c.append((l-r,l,r,k))
        c.sort(reverse=True)
        ans = 0
        for sa,p1,p2,k in c:
            if k > 0:
                u = query_max(1,k+1)
                if u > 0:
                    ans += p1
                    update_max(u,0)
                else:
                    ans += p2
            else:
                u = query_min(abs(k)+1,N+1)
                if u < N+1:
                    ans += p1
                    update_max(u,N+1)
                else:
                    ans += p2
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
t = int(input())
for i in range(t):
    n = int(input())
    a1 = []
    a2 = []
    ans = 0
    flag = [False] * n
    for j in range(n):
        k, l, r = map(int, input().split())
        if l > r:
            a1.append([k, l, r])
        elif l < r:
            a2.append([n - k, r, l])
        else:
            ans += l
    a1.sort(key = lambda x: x[1] - x[2], reverse = True)
    a2.sort(key = lambda x: x[1] - x[2], reverse = True)
    for j in range(len(a1)):
        num = a1[j][0] - 1
        while num >= 0:
            if flag[num] == False:
                flag[num] = True
                ans += a1[j][1]
                break
            else:
                num -= 1
        else:
            ans += a1[j][2]
    for j in range(len(a2)):
        num = a2[j][0] - 1
        while num >= 0:
            if flag[num] == False:
                flag[num] = True
                ans += a2[j][1]
                break
            else:
                num -= 1
        else:
            ans += a2[j][2]
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq

class BinaryIndexedTree:
    # Initialize BIT with non-zero value
    def __init__(self, array):
        self.len = len(array)
        self.data = [0] + array
        self.build()

    def build(self):
        for i in range(1, self.len):
            if i + (i & -i) > self.len:
                continue
            self.data[i + (i & -i)] += self.data[i]

    # Add w to a[x] (0-indexed)
    def add(self, x, w):
        x += 1
        while x <= self.len:
            self.data[x] += w
            x += x & -x

    # Get Sum of a[0 : x) (0-indexed)
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.data[x]
            x -= x & -x
        return ret

    # Get first index s.t. sum a[0 : index) >= w
    def bisect_left(self, w):
        if w <= 0:
            return 0
        x = 0
        delta = pow(2, (self.len - 1).bit_length())
        while delta > 0:
            if x + delta <= self.len and self.data[x + delta] < w:
                w -= self.data[x + delta]
                x += delta
            delta >>= 1
        return x

t = int(input())
for _ in range(t):
    n = int(input())
    q = []
    base = 0
    left = BinaryIndexedTree([0] * n)
    right = BinaryIndexedTree([0] * n)
    left_bag = [[] for _ in range(n)]
    right_bag = [[] for _ in range(n)]
    for _ in range(n):
        k, l, r = map(int, input().split())
        if k == n:
            base += l
            continue
        if l == r:
            base += l
        elif l > r:
            q.append((l-r, 0, k-1))
            base += r
            left_bag[k-1].append(l-r)
        else:
            q.append((r-l, 1, n-k-1))
            base += l
            right_bag[n-k-1].append(r-l)
    
    left_bag.reverse()
    hq = []
    for bag in left_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, item)
        if hq:
            base += hq.pop()
    right_bag.reverse()
    hq = []
    for bag in right_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, item)
        if hq:
            base += hq.pop()
    print(base)

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
  N = int(input())
  LHdef = [[] for j in range(N+1)]
  LHcount = [0 for j in range(N+1)]
  LHsum = 0
  RHdef = [[] for j in range(N+1)]
  RHcount = [0 for j in range(N+1)]
  RHsum = 0
  for i in range(N):
    
    K, L, R = map(int, input().split())
    
    if L >= R:
      #print("L",K, L ,R)
      LHdef[K].append(L-R)
      LHcount[K] += 1
      LHsum += L
    else:
      #print("R", N-K, L ,R)
      RHdef[N-K].append(R-L)
      RHcount[N-K] += 1
      RHsum += R
  dans = 0
  #print(LHdef, LHcount, LHsum)
  #print(RHdef, RHcount, RHsum)
  for i in range(N):
    if i == 0:
      if RHcount[i]>0:
        dans += sum(RHdef[i])
        RHcount[i]=0
    else:
      LHcount[i] = LHcount[i] + LHcount[i-1]
      if LHcount[i]>i:
        dans += sum(sorted(LHdef[i])[:LHcount[i]-i])
        LHcount[i]=i
      RHcount[i] = RHcount[i] + RHcount[i-1]
      if RHcount[i]>i:
        dans += sum(sorted(RHdef[i])[:RHcount[i]-i])
        RHcount[i]=i
  print(RHsum+LHsum-dans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq

class BinaryIndexedTree:
    # Initialize BIT with non-zero value
    def __init__(self, array):
        self.len = len(array)
        self.data = [0] + array
        self.build()

    def build(self):
        for i in range(1, self.len):
            if i + (i & -i) > self.len:
                continue
            self.data[i + (i & -i)] += self.data[i]

    # Add w to a[x] (0-indexed)
    def add(self, x, w):
        x += 1
        while x <= self.len:
            self.data[x] += w
            x += x & -x

    # Get Sum of a[0 : x) (0-indexed)
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.data[x]
            x -= x & -x
        return ret

    # Get first index s.t. sum a[0 : index) >= w
    def bisect_left(self, w):
        if w <= 0:
            return 0
        x = 0
        delta = pow(2, (self.len - 1).bit_length())
        while delta > 0:
            if x + delta <= self.len and self.data[x + delta] < w:
                w -= self.data[x + delta]
                x += delta
            delta >>= 1
        return x

t = int(input())
for _ in range(t):
    n = int(input())
    q = []
    base = 0
    left = BinaryIndexedTree([0] * n)
    right = BinaryIndexedTree([0] * n)
    left_bag = [[] for _ in range(n)]
    right_bag = [[] for _ in range(n)]
    for _ in range(n):
        k, l, r = map(int, input().split())
        if k == n:
            base += l
            continue
        if l == r:
            base += l
        elif l > r:
            q.append((l-r, 0, k-1))
            base += r
            left_bag[k-1].append(l-r)
        else:
            q.append((r-l, 1, n-k-1))
            base += l
            right_bag[n-k-1].append(r-l)
    
    left_bag.reverse()
    hq = []
    for bag in left_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, item)
        if hq:
            base += hq.pop()
    hq = []
    for bag in right_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, item)
        if hq:
            base += hq.pop()
    print(base)

Submission status: Wrong Answer

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from heapq import heappush,heappop
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
# mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

file=1




def possible(f,x):
    for i in range(x,0,-1):
        if f[i]==0:
            f[i]=1
            return 1
    return 0

    
def solve():


    for _ in range(ii()):
    
        n=ii()
        a=[]
        b=[]
        for i in range(n):
            x,y,z=mi()
            a.append([z-y,x,y,z])
        f=[0]*(n+1)
        ans=0
        c=1
        a.sort()
        x=[]
        y=[]
        for i in a:
            if i[0]<0:
                x.append([i[1],i[2],i[3]])
            else:
                y.append([i[1],i[2],i[3]])
        x.sort()
        y.sort(reverse=True)
        c=1
    
        for i in x:
            
            if(i[0]<c):
                x1=i[2]
            else:
                x1=i[1]
            c+=1
            ans+=x1

        for i in y:
           
            if i[0]<c:
                ans+=i[2]
            else:
                ans+=i[1]
            c+=1
        print(ans)




        
if __name__ =="__main__":

    if(file):

        if path.exists('input1.txt'):
            sys.stdin=open('input1.txt', 'r')
            sys.stdout=open('output1.txt','w')
        else:
            input=sys.stdin.readline
    solve()

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)
  data.sort(key=lambda x:-abs(x[1]-x[2]))
  ans = 0
  MAE = [i for i in range(N)]
  def CANSIT_MAE(x):
    if MAE[x] == -1:
      return -1
    elif MAE[x] == x:
      MAE[x] = x-1
      USHIRO[N-1-x] = N-1-x-1
      return x
    else:
      MAE[x] = CANSIT_MAE(MAE[x])
      if MAE[x] != -1:
        USHIRO[N-1-MAE[x]] = N-1-MAE[x]-1
      return MAE[x]
  USHIRO = [i for i in range(N)]
  def CANSIT_USHIRO(x):
    if USHIRO[x] == -1:
      return -1
    elif USHIRO[x] == x:
      USHIRO[x] = x-1
      MAE[N-1-x] = N-1-x-1
      return x
    else:
      USHIRO[x] = CANSIT_USHIRO(USHIRO[x])
      if USHIRO[x] != -1:
        MAE[N-1-USHIRO[x]] = N-1-USHIRO[x]-1
      return USHIRO[x]
  for K,L,R in data:
    if L==R or K==N:
      ans += L
    elif L>R:
      if CANSIT_MAE(K-1)!=-1:
        ans += L
      else:
        ans += R
    else:
      if CANSIT_USHIRO(N-1-K)!=-1:
        ans += R
      else:
        ans += L
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    T = Z()
    ans = []
    for _ in range(T):
        N = Z()
        camel1 = []
        camel2 = []
        for _ in range(N):
            k, l, r = ZZ()
            if l > r: camel1.append([k, -l, r])
            else: camel2.append([k, -r, l])
        camel1.sort()
        camel2.sort()
        order = 1
        cc = 0
        for i in range(len(camel1)):
            k, l, r = camel1[i]
            l = -l
            if order <= k: cc += l
            else: cc += r
            order += 1

        for i in range(len(camel2)):
            k, r, l = camel2[i]
            r = -r
            if order <= k: cc += l
            else: cc += r
            order += 1

        ans.append(cc)

    for a in ans:
        print(a)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


T = ni()

for _ in range(T):
    N = ni()
    ans = 0
    plus = []
    minus = []
    for _ in range(N):
        k, l, r = na()
        if l > r:
            plus.append([k, l-r])
            ans += r
        elif l < r:
            if N != k:
                minus.append([N-k, r-l])
            ans += l
        else:
            ans += l
    plus = sorted(plus, key=lambda x: x[0] * 10 ** 10 - x[1])
    minus = sorted(minus, key=lambda x: x[0] * 10 ** 10 - x[1])

    ans1 = ans
    queue = []
    for p in plus:
        i, v = p
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                queue[0] = v
    ans1 += sum(queue)
    queue = []
    for m in minus:
        i, v = m
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                queue[0] = v
    ans1 += sum(queue)

    ans2 = ans
    queue = []
    for p in plus:
        i, v = p
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                queue[0] = v
    ans2 += sum(queue)
    queue = []
    for m in minus:
        i, v = m
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                queue[0] = v
    ans2 += sum(queue)

    print(max(ans1, ans2))