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:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
from collections import deque
from collections import namedtuple
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


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


def main():
    T = INT()
    for t in range(T):
        solve()
    return

def solve():
    # 解説PDFの指針
    N = INT()
    left_camel = []
    right_camel = []
    camel = namedtuple("camel", "value, kth")
    ans = 0
    for k, l, r in ZIP(N):
        if l >= r:
            left_camel.append(camel(l-r, k))
            ans += r
        else:
            right_camel.append(camel(r-l, N-k))
            ans += l
    left_camel.sort(key=lambda x: x.kth)
    right_camel.sort(key=lambda x: x.kth)
    left_camel = deque(left_camel)
    right_camel = deque(right_camel)
    for camels in [left_camel, right_camel]:
        S = []
        while camels and camels[0].kth == 0:
            camels.popleft()
        for j in range(1, N+1):
            while camels and camels[0].kth == j:
                heappush(S, camels.popleft())
            while len(S) > j:
                heappop(S)
        while S:
            ans += heappop(S).value
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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 _ in range(T):

        N = NI()
        top = []
        bot = []

        ans = 0
        for _ in range(N):
            k,l,r = LI()
            ans += max(l,r)
            if l < r:
                bot.append((N-k,r-l))
            else:
                top.append((k,l-r))

        top.sort()
        bot.sort()

        q = []
        for k,v in top:
            heapq.heappush(q,v)
            if len(q) > k:
                vd = heapq.heappop(q)
                ans -= vd

        q = []
        for k,v in bot:
            heapq.heappush(q,v)
            if len(q) > k:
                vd = heapq.heappop(q)
                ans -= vd

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class OrderedSet:
    def __init__(self,n):
        self.c = {}
        self.r = {}
        #self.a_sort = sorted(list(set(a)))
        self.a_sort = list(range(n))
        for i,a in enumerate(self.a_sort):
            self.c[a] = i+1
            self.r[i+1] = a
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        self.num = [0]*self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self,x,k=1):
        index = self.c[x]
        self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    # xをk個削除する
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    # 格納しているxの数を返す
    def count(self,x):
        return self.num[self.c[x]-1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    # x以上の最小要素を返す
    def lower_bound(self,x):
        if x in self.c.keys():
            p = self.c[x]-1
        else:
            p = bisect_left(self.a_sort,x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    # x以下の最大要素を返す
    def upper_bound(self,x):
        if x in self.c.keys():
            p = self.c[x]
        else:
            p = bisect_right(self.a_sort,x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

T = I()

ans = []
for _ in range(T):
    N = I()
    K,L,R = LIR(N,3)
    
    left = []    # 左側に入れたい要素
    right = []   # 右側に入れたい要素
    for i in range(N):
        large = max(L[i],R[i])
        small = min(L[i],R[i])
        gap = large-small
        if L[i] >= R[i]:
            left.append((gap,K[i]-1,large,small))
        else:
            right.append((gap,K[i],large,small))

    left.sort(key=lambda x:x[0], reverse=True)
    right.sort(key=lambda x:x[0], reverse=True)

    ordset = OrderedSet(N)
    ans_t = 0

    # まだ空いている場所をordsetに入れておく
    for i in range(N):
        ordset.insert(i)

    for i in range(len(left)):
        p = ordset.upper_bound(left[i][1])
        if p is None:
            p2 = ordset.upper_bound(len(left)-1)
            ordset.erase(p2)
            ans_t += left[i][3]
        elif p >= len(left):
            p2 = ordset.upper_bound(len(left)-1)
            ordset.erase(p2)
            ans_t += left[i][2]            
        else:
            ordset.erase(p)
            ans_t += left[i][2]

    for i in range(len(right)):
        p = ordset.lower_bound(right[i][1])
        if p is None:
            p2 = ordset.lower_bound(len(left))
            ordset.erase(p2)
            ans_t += right[i][3]
        else:
            ordset.erase(p)
            ans_t += right[i][2]
    
    ans.append(ans_t)

for ans_t in ans:
    print(ans_t)

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop

T = int(input())
for _ in range(T):
  N = int(input())
  base = 0
  A = []
  C = []
  B = [0 for _ in range(N)]
  Q = []
  S = []
  for i in range(N):
    K, L, R = map(int,input().split()) 
    tmp = min(L, R)
    K -= 1
    if L > R:
      A.append((K,L-R))
    if R >= L:
      if K < N - 1:
        C.append((N-2-K,R-L))
    base += tmp
  A.sort(reverse = True)
  C.sort(reverse = True)
  #print(base)
  #print(A,C)
  
  for i in range(N):
    if len(A) == 0:
      break
    while A[-1][0] == i:
      a = A[-1][1] 
      A.pop()
      heappush(Q, a)
      if len(A) == 0:
        break
    while i+1 < len(Q):
      heappop(Q)
      if len(Q) == 0:
        break
  
  for i in range(N):
    if len(C) == 0:
      break
    while C[-1][0] == i:
      a = C[-1][1] 
      C.pop()
      heappush(S, a)
      if len(C) == 0:
        break
    while i+1 < len(S):
      heappop(S)
      if len(S) == 0:
        break
      
  print(base + sum(Q) + sum(S))
     
  """
  l = 0
  r = N-1
  for a in A:
    if a[2] == 0:
      if l < a[0]:
        l += 1
        base += a[1] 
    else:
      if r >= N-a[0]:
        r -= 1
        base += a[1]
  print(base)
  """
#print(A)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
from collections import deque
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


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


def main():
    T = INT()
    for t in range(T):
        solve()
    return

def solve():
    # 解説PDFの指針
    N = INT()
    left_camel = []
    right_camel = []
    ans = 0
    for k, l, r in ZIP(N):
        if l >= r:
            left_camel.append((l-r, k))
            ans += r
        else:
            right_camel.append((r-l, N-k))
            ans += l
    left_camel.sort(key=lambda x: x[1])
    right_camel.sort(key=lambda x: x[1])
    left_camel = deque(left_camel)
    right_camel = deque(right_camel)
    # print(left_camel, right_camel)
    for camels in [left_camel, right_camel]:
        S = []
        while len(camels) > 0 and camels[0][1] == 0:
            camels.popleft()
        for j in range(1, N+1):
            while len(camels) > 0 and camels[0][1] == j:
                heappush(S, camels.popleft())
            while len(S) > j:
                heappop(S)
        while S:
            ans += heappop(S)[0]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

T = int(input())
Ns = []
cases = []*T
for i in range(T):
    Ns.append(int(input()))
    cases.append([list(map(int, input().split())) for _ in range(Ns[-1])])

for i in range(T):
    answer = 0
    N = Ns[i]
    case = cases[i]
    
    sa = [case[j][2]-case[j][1] for j in range(N)]
    pluss = []
    minuss = []
    for j in range(N):
        if sa[j] >= 0:
            pluss.append([case[j][0],case[j][1],case[j][2],sa[j]])
        else:
            minuss.append([case[j][0],case[j][1],case[j][2],sa[j]])
    pluss = sorted(pluss)
    minuss = sorted(minuss,reverse = True)
    hq = []
    checking = 0
    for j in range(N-len(pluss),N):
        if checking < len(pluss):
            while j > pluss[checking][0]-1:
                heapq.heappush(hq, [-pluss[checking][3],pluss[checking][1],pluss[checking][2],pluss[checking][0]])
                checking+=1
                if checking >= len(pluss):
                    break
        if len(hq)>0:
            temp = heapq.heappop(hq)
            answer += temp[2]

    for j in range(checking,len(pluss)):
        heapq.heappush(hq, [-pluss[j][3],pluss[j][1],pluss[j][2],pluss[j][0]])
        
    for j in range(len(hq)):
        temp = heapq.heappop(hq)
        answer += temp[1]

    hq = []
    checking = 0
    for j in range(len(minuss)-1,-1,-1):
        if checking < len(minuss):
            while j <= minuss[checking][0]-1:
                heapq.heappush(hq, [minuss[checking][3],minuss[checking][1],minuss[checking][2],minuss[checking][0]])
                checking+=1
                if checking >= len(minuss):
                    break
        if len(hq)>0:
            temp = heapq.heappop(hq)
            answer += temp[1]

    for j in range(checking, len(minuss)):
                    heapq.heappush(hq, [minuss[j][3],minuss[j][1],minuss[j][2],minuss[j][0]])

    for j in range(len(hq)):
        temp = heapq.heappop(hq)
        answer += temp[2]
    print(answer)

Submission status: Accepted

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
for _ in range(int(input())):
  N = int(input())
  a = []
  mnsm = 0
  table = [[] for _ in range(N + 1)]
  ls = 0
  for _ in range(N):
    K, L, R = map(int, input().split())
    mnsm += min(L, R)
    a.append((K, L, R))
    if L >= R: table[K - 1].append((L, R))
    else: table[K].append((L, R))
    ls += L >= R
  h = []
  hh = []
  res = 0
  for i in range(N):
    for L, R in table[i]:
      if L >= R:
        hpush(h, L - R)
        res += L - R
    while len(h) > i + 1: res -= max(0, hpop(h))
  for i in range(N, -1, -1):
    for L, R in table[i]:
      if R > L:
        hpush(hh, R - L)
        res += R - L
    while len(hh) > N - i:
      res -= max(0, hpop(hh))
  print(mnsm + res)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    N = int(input())
    total = 0
    L, R = [], []
    for _ in range(N):
        k, l, r = map(int, input().split())
        if l >= r:
            # kより前に入れたい
            L.append((k, l, r))
            total += l
        else:
            # kより後ろに入れたい
            R.append((N - k, r, l))
            total += r

    # Lにとって前から，Rにとって後ろから
    L.sort()
    R.sort()

    queue = []
    for i in range(len(L)):
        k, ai, bi = L[i]
        heappush(queue, ai - bi)
        # 前から入れていき，効果が薄いもの(ai - bi)は消す
        while len(queue) > k:
            value = heappop(queue)
            total -= value
            
    queue = []
    for i in range(len(R)):
        k, ai, bi = R[i]
        heappush(queue, ai - bi)
        # 後ろから入れていき，効果が薄いもの(ai - bi)は消す
        while len(queue) > k:
            value = heappop(queue)
            total -= value

    print(total)


if __name__ == '__main__':
    t = int(input())
    while t > 0:
        t -= 1
        main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

from heapq import heappush, heappop

t = n_in()

for _ in range(t):
    n = n_in()

    sheeps = []
    for i in range(n):
        k,l,r = l_in()
        sheeps.append((i,k-1,l,r))


    res = 0
    base = 0

    memo = []
    for i in range(n):
        memo.append(set())

    base = 0
    for i,k,l,r in filter(lambda x: x[2] > x[3], sheeps):
        memo[k].add(i)
        base += r

    res += base

    q = []
        
    for pos in range(n):
        for s in memo[pos]:
            _,k,l,r = sheeps[s]
            heappush(q, (l-r, s))

        while len(q) > pos+1:
            heappop(q)

    for delta, i in q:
        res += delta

        
    memo = [set() for _ in range(n+1)]

    base = 0
    for i,k,l,r in filter(lambda x: x[2] <= x[3], sheeps):
        memo[k+1].add(i)
        base += l

    res += base

    q = []
        
    for pos in reversed(range(n)):
        for s in memo[pos]:
            _,k,l,r = sheeps[s]
            heappush(q, (r-l, s))

        while len(q) > n-pos:
            heappop(q)
    for delta, i in q:
        res += delta

    print(res)

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappop, heappush

    def greedy(L):
        ret = 0
        q = []
        for k, gain in L:
            for g in gain:
                ret += g
                heappush(q, g)
            while len(q) > k:
                g = heappop(q)
                ret -= g
        return ret

    for _ in [0]*int(input()):
        N = int(input())

        ans = 0
        pos = defaultdict(list)
        neg = defaultdict(list)
        for _ in range(N):
            K, L, R = map(int, input().split())
            if L > R:
                ans += R
                pos[K].append(L-R)
            elif L < R:
                ans += L
                neg[N-K].append(R-L)
            else:
                ans += L

        pos = sorted(pos.items())
        neg = sorted(neg.items())
        ans += greedy(pos)
        ans += greedy(neg)

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import *
input = sys.stdin.readline

def get_happiness(camels):
    camels.sort(reverse=True)
    N = len(camels)
    ret = 0

    hq = []
    for i in range(1, N + 1):
        while camels and camels[-1][0] == i:
            _, diff = camels.pop()
            heappush(hq, diff)
        while len(hq) > i:
            heappop(hq)

    while camels:
        _, diff = camels.pop()
        ret += diff

    ret += sum(hq)

    return ret


def solution():
    N = int(input())
    left_camels = []
    right_camels = []
    left_sum = 0
    right_sum = 0
    for i in range(N):
        K, L, R = map(int, input().split())
        if L >= R:
            left_sum += R
            left_camels.append((K, L - R))
        else:
            right_sum += L
            if K == N: continue
            right_camels.append((N - K, R - L))
    answer = 0
    answer += left_sum + get_happiness(left_camels)
    answer += right_sum + get_happiness(right_camels)
    print(answer)

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solution()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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:h=[];s+=sum(heappush(h,l-r)or l-(k<len(h)and heappop(h))for k,l,r in sorted(x))
 print(s)

Submission status: Accepted

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:
  h=[]
  for k,l,r in sorted(x):heappush(h,l-r);s+=l-(k<len(h)and heappop(h))
 print(s)

Submission status: Accepted

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:
  h=[]
  for k,l,r in sorted(x):s+=l;heappush(h,l-r);s-=k<len(h)and heappop(h)
 print(s)

Submission status: Accepted

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:
  h=[]
  for k,l,r in sorted(x):
   s+=l;heappush(h,l-r)
   if len(h)>k:s-=heappop(h)
 print(s)

Submission status: Accepted

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:
  h=[]
  for k,l,r in sorted(x):
   s+=r
   if k:s+=l-r;heappush(h,l-r)
   if len(h)>k:s-=heappop(h)
 print(s)

Submission status: Accepted

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:
   s+=r
   if k:s+=l-r;heappush(h,l-r)
   if len(h)>k:s-=heappop(h)
 print(s)

Submission status: Accepted

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:s+=l;heappush(h,l-r)
   else:s+=r
   if len(h)>k:s-=heappop(h)
 print(s)

Submission status: Accepted

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

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+=[[k,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: Accepted

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+=[[k,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: Accepted

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

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)


# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #
t = inn()
for tt in range(t):
    #ddprint(f"{tt=}")
    n = inn()
    klr = []
    nl = 0
    for i in range(n):
        k,l,r = inm()
        klr.append((abs(l-r),(-k if l>r else -(n+1-k)),i,k,l,r))
        if l>r:
            nl += 1
    klrc = [z for z in klr]
    klr.sort(reverse=True)
    h = {}
    tol = Segtree(n,-1,lambda x,y: max(x,y))
    tor = Segtree(n,n+1,lambda x,y: min(x,y))
    tol.setary(list(range(n)))
    tor.setary(list(range(n)))
    for j in range(n):
        v,w,i,k,l,r = klr[j]
        if k==n:
            continue
        if l>r:
            x = min(nl-1,k-1)
            m = tol.query(0,x+1)
            if m<0:
                continue
            tol.set(m,-1)
            h[m] = i
        else:
            x = max(nl,k)
            m = tor.query(x,n)
            if m>n:
                continue
            tor.set(m,n+1)
            h[m] = i
        #ddprint(f"{j=} {i=} {x=} {m=} {k=} {l=} {r=} {v=} {w=}")
    #ddprint(f"h1 {h}")
    put = {}
    for x in h:
        put[h[x]] = 1
    top = 0
    for i in range(n):
        if i in put:
            continue
        while top in h:
            top += 1
        h[top] = i
    #ddprint(f"h2 {h}")
    rev = [-1]*n
    sm = 0
    for i in range(n):
        j = h[i]
        v,w,ii,k,l,r = klrc[j]
        sm += l if i<=k-1 else r
        #ddprint(f"{i=} {j=} {k=} {sm=}")
    print(sm)

Submission status: Accepted

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,*h=len(x),
  while h or x:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[~(n>0)]
   n-=1
 print(s)

Submission status: Accepted

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,*h=len(x),
  while h or x:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[2-(n>0)]
   n-=1
 print(s)

Submission status: Accepted

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,*h=len(x),
  while n:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=1
  for*_,r in x+h:s+=r
 print(s)

Submission status: Accepted

Solution code:
from heapq import*
i=input
for*x,_ in'_'*int(i()):
 n,s,*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:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=1
  for*_,r in x+h:s+=r
 print(s)

Submission status: Accepted

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:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=1
  for*_,r in x+h:s+=r
 print(s)

Submission status: Accepted

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:
   while[[n,0,0]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=1
  for*_,r in x+h:s+=r
 print(s)

Submission status: Accepted

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

    print(ans)

Submission status: Accepted

Solution code:
import heapq

T = int(input())

for _ in range(T):
  N = int(input())
  rlt = 0
  dicl = {}
  dicr = {}
  Ls = []
  Rs = []
  mkl = 0
  mkr = 0
  for i in range(1,N+1):
    k, l, r = map(int, input().split())
    rlt += min(l, r)
    if l > r:
      if k not in dicl:
        dicl[k] = [l-r]
      else:
        dicl[k].append(l-r)
      mkl = max(mkl, k)
    else:
      if N-k not in dicr:
        dicr[N-k] = [r-l]
      else:
        dicr[N-k].append(r-l)
      mkr = max(mkr, N-k)

  for i in range(1,mkl+1):
    if i in dicl:
      for j in dicl[i]:
        heapq.heappush(Ls, j)
        rlt += j
    while len(Ls) > i:
      t = heapq.heappop(Ls)
      rlt -= t
  for i in range(1,mkr+1):
    if i in dicr:
      for j in dicr[i]:
        heapq.heappush(Rs, j)
        rlt += j
    while len(Rs) > i:
      t = heapq.heappop(Rs)
      rlt -= t
      
  print(rlt)

Submission status: Accepted

Solution code:
from heapq import*
i=input
c=int(i())
while c:
 n=m=int(i());s,x,*y=0,[]
 while m:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[(n-k,r,l)]*(l<=r);m-=1
 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);c-=1