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: Accepted

Solution code:
import bisect
T=int(input())
class Segtree(object):
    def __init__(self, init_val, N):
        self.func = self.segfunc_max
        self.ide_ele = 0 # max

        self.num = 2**(N-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        self.init_val = init_val

        n = len(self.init_val)
        self.seg[self.num-1:n+self.num-1] = self.init_val[:n]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return -1
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if self.seg[p]==0 and self.seg[q]==0:
                return -1
            elif self.seg[q]==0:
                q = (q-1)//2
                res = self.seg[p]
                continue
            else:
                res = self.seg[q]
                p = p//2
                continue
        if p == q:
            # res = self.func(res,self.seg[p])
            res = -1
        return res
    def query2(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.func(res,self.seg[p])
            if q&1 == 1:
                res = self.func(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res,self.seg[p])
        else:
            res = self.func(self.func(res,self.seg[p]),self.seg[q])
        return res
    def segfunc_max(self, a, b):
        if a >= b:
            return a
        return b

for t in range(T):
    N=int(input())
    KLR = [tuple(map(int,input().split())) for _ in range(N)]
    DKLR2 = [(R-L, K, i) for i,(K,L,R) in enumerate(KLR) if R-L>0]
    DKLR = [(L-R, K, i) for i,(K,L,R) in enumerate(KLR) if R-L<=0]
    DKLR = sorted(DKLR, reverse=True)
    DKLR2 = sorted(DKLR2, reverse=True)
    res = 0
    L1 = len(DKLR)
    L2 = len(DKLR2)
    left = list(range(1,L1+1))
    right = list(range(1,L2+1))
    seg1 = Segtree(left,L1)
    seg2 = Segtree(right,L2)
    # print(DKLR)
    # print(DKLR2)
    for dv,k,i in DKLR:
        # print(seg1.seg)
        if k <= L1:
            idx = seg1.query2(0,k)-1
            # print(idx)
            if idx!=-1:
                seg1.update(idx, 0)
                res += KLR[i][1]
            else:
                res += KLR[i][2]
        else:
            res += KLR[i][1]
    for dv,k,i in DKLR2:
        # print(seg2.seg)
        if k >= N-L2:
            idx = seg2.query2(0,N-k)-1
            # print(idx)
            if idx!=-1:
                seg2.update(idx, 0)
                res += KLR[i][2]
            else:
                res += KLR[i][1]
        else:
            res += KLR[i][2]
    # for dv,k,i in DKLR2:
    #     idx = seg2.query2(0,k)
    #     if idx!=-1:
    #         seg2.update(idx, 0)
    #         res += KLR[i][2]
    #     else:
    #         res += KLR[i][1]
    print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
import heapq  
def calc(A):
    n = len(A)
    c = 0
    h = []
    ret = 0
    for i, aa in enumerate(A):
        for a in aa:
            ret += a
            heapq.heappush(h, a)
            if len(h) > i + 1:
                ret -= heapq.heappop(h)
    return ret

T = int(input())
for _ in range(T):
    N = int(input())
    L = [[] for _ in range(N)]
    R = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        k, l, r = map(int, input().split())
        if k == N:
            ans += l
        elif l == r:
            ans += l
        elif l < r:
            ans += l
            R[N-1-k].append(r - l)
        else:
            ans += r
            L[k-1].append(l - r)
    ans += calc(L) + calc(R)
    print(ans)

Submission status: Accepted

Solution code:
import heapq
def solve():
    N = int(input())
    klr = [list(map(int,input().split())) for _ in range(N)]
    
    ll = []
    lr = []
    for i in range(N):
        if klr[i][1]>klr[i][2]:
            ll.append(klr[i])
        else:
            lr.append(klr[i])

    ansl = 0
    ll.sort(key=lambda x:-x[0])
    j = 0
    cand = []
    for i in range(len(ll)-1,-1,-1):
        while j<len(ll):
            if ll[j][0]-1<i:
                break
            heapq.heappush(cand,[ll[j][2]-ll[j][1],ll[j][0],ll[j][1],ll[j][2]])
            j += 1
        if cand:
            d,k,l,r = heapq.heappop(cand)
            ansl += l
    while cand:
        d,k,l,r = heapq.heappop(cand)
        ansl += r

    ansr = 0
    lr.sort(key=lambda x:x[0])
    j = 0
    cand = []
    for i in range(len(ll),N+1):
        while j<len(lr):
            if lr[j][0]>i:
                break
            heapq.heappush(cand,[-lr[j][2]+lr[j][1],lr[j][0],lr[j][1],lr[j][2]])
            j += 1
        if cand and i!=N:
            d,k,l,r = heapq.heappop(cand)
            ansr += r
    while cand:
        d,k,l,r = heapq.heappop(cand)
        ansr += l
    ans = ansl+ansr
    print(ans)

T = int(input())
for t in range(T):
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop, heappush

t = int(input())
for i in range(t):
    n = int(input())
    C = [list(map(int,input().split())) for i in range(n)]
    L = []
    R = []

    ans = 0
    for i in range(n):
        k = C[i][0]-1
        l = C[i][1]
        r = C[i][2]
        ans += min(l,r)
        if l > r:
            L.append([r-l, k])
        elif l < r:
            R.append([l-r, k+1])

    L.sort(key=lambda x:x[1], reverse=True)
    R.sort(key=lambda x:x[1])

    LQ = []
    ind = 0
    for i in range(n-1,-1,-1):
        while ind < len(L) and L[ind][1] == i:
            heappush(LQ, L[ind])
            ind += 1
        if len(LQ) > 0:
            LL = heappop(LQ)
            ans += -LL[0]

    RQ = []
    ind = 0
    for i in range(n):
        while ind < len(R) and R[ind][1] == i:
            heappush(RQ, R[ind])
            ind += 1
        if len(RQ) > 0:
            RR = heappop(RQ)
            ans += -RR[0]
    # print(LQ,RQ)
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

T = int(input())


def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
def init_min(init_min_val):
    #set_val
    for i in range(n):
        seg_min[i+num_min-1]=init_min_val[i]    
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2])
def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res

#####単位元######
ide_ele_max = -1
#####単位元######
ide_ele_min = 10**10


dg = 10**6

for testcase in range(T):
    n = int(input())
    #num_max:n以上の最小の2のべき乗
    num_max =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max
    #num_min:n以上の最小の2のべき乗
    num_min =2**(n-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min
    init_min(list(range(n)))
    init_max(list(range(n)))

    res = 0
    tank = []
    res = 0
    for i in range(n):
        K,L,R = map(int,input().split())
        K -= 1
        if L <= R:
            tank.append((R-L)*dg+K*2+1)
            res += L
        else:
            tank.append((L-R)*dg+K*2)
            res += R
    tank.sort(reverse = True)
    s = 0
    for e in tank:
        pt,amari = divmod(e,dg)
        idx,right = divmod(amari,2)
        if right == 0:
            kk = query_max(0,idx+1)
            if kk != -1:
                res += pt
                update_max(kk,-1)
        else:
            kk = query_min(idx+1,n)
            if kk != 10**10:
                res += pt
                update_min(kk,10**19)

    print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
T = int(input())

for _ in range(T):
    N = int(input())
    arr1 = []
    arr2 = []
    for _ in range(N):
        K, L, R = list(map(int, input().split()))
        if L > R:
            arr1.append((K, L, R))
        else:
            arr2.append((N-K, R, L))

    arr1.sort()
    baseS = 0
    diffS = 0
    q = []
    length = 0
    for K, L, R in arr1:
        baseS += R
        diff = L - R
        heappush(q, diff)
        diffS += diff
        length += 1
        while length > K:
            d = heappop(q)
            diffS -= d
            length -= 1
    ans = baseS + diffS

    arr2.sort()
    baseS = 0
    diffS = 0
    q = []
    length = 0
    for K, L, R in arr2:
        baseS += R
        diff = L - R
        heappush(q, diff)
        diffS += diff
        length += 1
        while length > K:
            d = heappop(q)
            diffS -= d
            length -= 1
    ans += baseS + diffS
    print(ans)

Submission status: Accepted

Solution code:
# Fast IO (only use in integer input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

import heapq

T = int(input())
for _ in range(T):
    N = int(input())
    frontCamel = []
    backCamel = []
    indifferentCamel = []
    Happiness = 0
    for _ in range(N):
        k,l,r = map(int,input().split())
        if l > r:
            frontCamel.append((k,l-r))
            Happiness += r
        elif r > l:
            backCamel.append((N-k,r-l))
            Happiness += l
        else:
            indifferentCamel.append((k,0))
            Happiness += l
    frontQ = []
    backQ = []
    frontCamel.sort(key = lambda x:x[0])
    backCamel.sort(key = lambda x:x[0])
    for Camel in frontCamel:
        if Camel[0] == 0:
            continue
        if Camel[0] > len(frontQ):
            heapq.heappush(frontQ,Camel[1])
        else:
            if frontQ[0] < Camel[1]:
                heapq.heapreplace(frontQ,Camel[1])
    for Camel in backCamel:
        if Camel[0] == 0:
            continue
        if Camel[0] > len(backQ):
            heapq.heappush(backQ,Camel[1])
        else:
            if backQ[0] < Camel[1]:
                heapq.heapreplace(backQ,Camel[1])
    Happiness += sum(frontQ)
    Happiness += sum(backQ)
    print(Happiness)

Submission status: Accepted

Solution code:
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def popcnt0(n):
        c = 0
        for i in range(20):
            c += (n >> i) & 1
        return c
    def cnt(num):
        c = 0
        while(num>0):
            #num %= bin(num).count("1")
            num %= popcnt0(num)
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        else:
            ans[-1] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(1)
        return
    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)
    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i] + 2*(bit -1)) % (bit-1)
            ans[i] = cnt(cur)+1
        #print(cur)

    for v in ans:
        print(v)
    return

def examE():
    T = I()
    ans = [0]*T

    for t in range(T):
        N = I()
        KLR = [LI()for _ in range(N)]
        L = [[]for _ in range(N)]; R = [[]for _ in range(N)]
        for k,l,r in KLR:
            if l<r:
                ans[t] += l
                if k==N:
                    continue
                R[k].append(r-l)
            elif r<l:
                L[k-1].append(l-r)
                ans[t] += r
            else:
                ans[t] += l
        #print(ans[t])
        #print(L)
        #print(R)
        que = []
        for i in range(N)[::-1]:
            for l in L[i]:
                heappush(que,-l)
            if que:
                ans[t] += -heappop(que)
        que = []
        for i in range(N):
            for r in R[i]:
                heappush(que,-r)
            if que:
                ans[t] += -heappop(que)

    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import heapq

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        KLR = [tuple(map(int, input().split())) for _ in range(N)]
        KLR.sort()
        H = []
        T = []
        s = 0
        for k, l, r in KLR:
            s += r
            if l - r >= 0:
                heapq.heappush(H, (l - r, k))
                while len(H) > k:
                    T.append(heapq.heappop(H))
            else:
                T.append((l - r, k))
        s += sum(l for l, k in H)
        H = []
        T.sort(key = lambda x: -x[1])
        for l, k in T:
            heapq.heappush(H, (-l, N - k))
            while len(H) > N - k:
                s -= heapq.heappop(H)[0]

        print(s)
main()

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(N, K, L, R):
    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    score = 0
    for k, l, r in zip(K, L, R):
        k -= 1
        if l < r:
            score += l
            right[k].append(r - l)
        else:
            score += r
            left[k].append(l - r)
    q = []
    for n, xs in enumerate(left, 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    q = []
    for n, xs in enumerate(right[::-1][1:], 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    return score

T = int(readline())
for _ in range(T):
    N = int(readline())
    K, L, R = [], [], []
    for _ in range(N):
        k, l, r = map(int, readline().split())
        K.append(k)
        L.append(l)
        R.append(r)
    print(main(N, K, L, R))

Submission status: Accepted

Solution code:
import sys
import heapq as hq

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    f = list()
    g = list()
    ans = 0
    for i in range(n):
        k, l, r = nm()
        if l > r:
            ans += r
            g.append((k, l-r))
        else:
            ans += l
            f.append((k+1, r-l))
    g.sort()
    f.sort(reverse=True)
    h = list()
    # print(f)
    # print(g)
    for k in range(len(g), 0, -1):
        while g and g[-1][0] >= k:
            _, c = g.pop()
            hq.heappush(h, -c)
        if h:
            ans -= hq.heappop(h)
    h = list()
    for k in range(len(g)+1, n+1):
        while f and f[-1][0] <= k:
            _, c = f.pop()
            hq.heappush(h, -c)
        if h:
            ans -= hq.heappop(h)
    print(ans)
    return

T = ni()
for _ in range(T):
    solve()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    for _ in range(int(input())):
        N = int(input())
        Llike = []
        Rlike = []
        ans = 0
        for _ in range(N):
            k, l, r = map(int, input().split())
            if l > r:
                Llike.append([l-r, k])
                ans += l
            elif r > l:
                if k == N:
                    ans += l
                else:
                    Rlike.append([r-l, N-k])
                    ans += r
            else:
                ans += r
        bitL = Bit(len(Llike))
        bitR = Bit(len(Rlike))
        Llike.sort(key=lambda x: x[0], reverse=True)
        Rlike.sort(key=lambda x: x[0], reverse=True)
        for i in range(len(Llike)):
            bitL.add(i+1, 1)
        for i in range(len(Rlike)):
            bitR.add(i+1, 1)
        for v, k in Llike:
            if k > len(Llike):
                k = len(Llike)
            u = bitL.sum(k)
            if u == 0:
                ans -= v
                j = bitL.lower_bound(bitL.sum(len(Llike)))
                bitL.add(j, -1)
            else:
                j = bitL.lower_bound(u)
                bitL.add(j, -1)
        for v, k in Rlike:
            if k > len(Rlike):
                k = len(Rlike)
            u = bitR.sum(k)
            if u == 0:
                ans -= v
                j = bitR.lower_bound(bitR.sum(len(Rlike)))
                bitR.add(j, -1)
            else:
                j = bitR.lower_bound(u)
                bitR.add(j, -1)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

TT = int(input())
import heapq

for loop in range(TT):

    N = int(input())

    L = []
    R = []

    abmax = 0

    for i in range(N):

        k,l,r = map(int,input().split())

        if l >= r:
            L.append( (k,l,r) )
            abmax += l
        else:
            R.append( (N-k,r,l) )
            abmax += r

    L.sort()
    R.sort()

    q = []
    for i in range(len(L)):

        k,nowc,nexc = L[i]
        heapq.heappush( q , nowc-nexc )

        while len(q) > k:
            tmp = heapq.heappop(q)
            abmax -= tmp

    q = []
    for i in range(len(R)):

        k,nowc,nexc = R[i]
        heapq.heappush( q , nowc-nexc )

        while len(q) > k:
            tmp = heapq.heappop(q)
            abmax -= tmp

    print (abmax)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq as hp

Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    KLR = [list(map(int, input().split())) for _ in range(N)]
    Query.append((N, KLR))

for N, KLR in Query:
    basic = 0
    Ls = [[] for _ in range(N)]
    Rs = [[] for _ in range(N)] 
    for k, l, r in KLR:
        if l > r:
            basic += r
            Ls[k-1].append(l-r)
        elif r > l:
            if k != N:
                basic += l
                Rs[k].append(r-l)
            else:
                basic += l
        else:
            basic += r
    
    ans = basic
    q1 = []
    for i in reversed(range(N)):
        for l in Ls[i]:
            hp.heappush(q1, -l)
        if q1:
            p = -hp.heappop(q1)
            ans += p
    
    q2 = []
    for i in range(N):
        for r in Rs[i]:
            hp.heappush(q2, -r)
        if q2:
            p = -hp.heappop(q2)
            ans += p
    
    print(ans)