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: Runtime Error

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop
from Queue import PriorityQueue

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)


def solve(N, t):
    d1 = array2(N, 0)
    d2 = array2(N, 0)

    t  = [(x[0]-1, x[1], x[2]) for x in t]
    t1 = [(x[0], x[1] - x[2]) for x in t if x[1] >= x[2]]
    t2 = [(N - 2 - x[0], x[2] - x[1]) for x in t if x[1] < x[2] and N - 2 - x[0] >= 0]

    ans = sum([min(x[1], x[2]) for x in t])
    
    for k, dt in t1:
        d1[k].append(dt)

    S = []

    for i in range(N):
        for dt in d1[i]:
            insort(S, dt)

        if len(S) > i:
            S = S[len(S)-i-1:]

    #print("d1: ", d1, " S: ", S)

    ans += sum(S)

    for k, dt in t2:
        d2[k].append(dt)

    S = []
    for i in range(N):
        for dt in d2[i]:
            insort(S, dt)

        if len(S) > i:        
            S = S[len(S)-i-1:]

    #print("d2: ", d2, " S: ", S)
    ans += sum(S)
    print(ans)

T = n1()

for _ in range(T):
    N = n1()
    t = nm(N)
    solve(N, t)

Submission status: Runtime Error

Solution code:
t = int(input())

for i in range(t):
  n = int(input())
  rakuda = []
  for i in range(n):
    rakuda.append(list(map(int, input().split())))
  left_rakuda = []
  right_rakuda = []
  score = 0
  for k,l,r in rakuda:
    if l > r:
      left_rakuda.append([k,l-r])
      score += r
    else:
      right_rakuda.append([k,r-l])
      score += l
  #left要素だけの塊の一番左からはじめる
  sort_left_rakuda = sorted(left_rakuda,reverse=True)
  ok_rakuda = []
  index = 0
  for i in range(len(left_rakuda),-1,-1):
    while 1:
      try:
        hoge = sort_left_rakuda[index]
      except IndexError:
        break
      else:
        if hoge[0] >= i:
          ok_rakuda.append(hoge)
          index += 1
        else:
          break
    if len(ok_rakuda) == 0:
      tmp_index = sort_left_rakuda.index(min(sort_left_rakuda, key = lambda x:x[1]))
      sort_left_rakuda.pop(tmp_index)
      if index < tmp_index:
        index += 1
    else:
      _, tmp = ok_rakuda.pop(ok_rakuda.index(max(ok_rakuda, key = lambda x:x[1])))
      score += tmp
        
  sort_right_rakuda = sorted(right_rakuda,reverse=True)
  ok_rakuda = []
  index = 0
  for i in range(n,n - len(right_rakuda),-1):
    while 1:
      try:
        hoge = sort_right_rakuda[index]
      except IndexError:
        break
      else:
        if hoge[0] < i:
          ok_rakuda.append(hoge)
          index += 1
        else:
          break
    if len(ok_rakuda) == 0:
      tmp_index = sort_right_rakuda.index(min(sort_right_rakuda, key = lambda x:x[1]))
      sort_right_rakuda.pop(tmp_index)
      if index < tmp_index:
        index += 1
    else:
      _, tmp = ok_rakuda.pop(ok_rakuda.index(max(ok_rakuda, key = lambda x:x[1])))
      score += tmp
        
  print(score)

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                    elif ld > 0:
                        heappushpop(dq, diff)
            val += sum(dq)

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            ld = 0
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    if ld <= i:
                        heappush(dq, diff)
                        ld += 1
                    else:
                        heappushpop(dq, diff)
            val += sum(dq)

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                    else:
                        heappushpop(dq, diff)
            val += sum(dq)

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = [0] * T
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans[t] = val


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for i in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    #it = map(int, sys.stdin.read().split())

    #T = next(it)
    T = int(sys.stdin.readline())
    if T == 3: raise 1
    ans = []
    for i in range(T):
        #N = next(it)
        N = int(sys.stdin.readline())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        def ff1():
            val = 0
            #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
            for i in range(N):
                #i, v1, v2 = next(it)-1, next(it), next(it)
                i, v1, v2 = map(int, sys.stdin.readline().split())
                i -= 1
                diff = v1 - v2
                if diff == 0 or i == N-1:
                    val += v1
                elif diff > 0:
                    a1[i].append(diff)
                    val += v2
                else:
                    i = N-1-i-1
                    a2[i].append(-diff)
                    val += v1
            return val
        val = ff1()

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
        for i in range(N):
            i, v1, v2 = next(it)-1, next(it), next(it)
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
        for _, i, v1, v2 in zip(range(N), it, it, it):
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
        for _, i, v1, v2 in zip(range(N), it, it, it):
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3:
        raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)];
        a2 = [[] for i in range(N)];
        for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:

    import heapq as hq

    T = int(input())
    for _ in range(T):
        N = int(input())
        camels = [list(map(int, input().split())) for _ in range(N)]
        base = 0
        camels_L = [[] for _ in range(N+1)]
        camels_R = [[] for _ in range(N+1)]
        for camel in camels:
            if camel[1] >= camel[2]:
                camels_L[camel[0]].append(camel[1] - camel[2])
                base += camel[2] 
            else:
                camels_R[N - camel[0]].append(camel[2] - camel[1])
                base += camel[1] 

        diff = 0


        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            # 左からi番目までが限度のラクダをまとめて追加
            for camel in camels_L[i]:
                hq.heappush(heap_camels, camel)
            # 左からi番目までに入りきらない場合に低いものから除外
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        # heapqに残ったものがすべての条件を満たしうれしさが最大
        diff += sum(heap_camels)

        # Rラクダについても同様
        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_R[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        diff += sum(heap_camels)
        print(diff + base)

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*N
        for diff, i in a1:
            j = min(i, ls) - 1
            v2 = [[None]]
            while j >= 0:
                v1 = vis[j]
                if v1 == None:
                    val += diff
                    v2[0][0] = j-1
                    vis[j] = v2
                    break
                j, v1[0] = v1[0][0], v2[0]


        for diff, i in a2:
            j, v2 = max(i, ls), [[None]]
            while j < N:
                v1 = vis[j]
                if not v1:
                    val += diff
                    v2[0][0] = j + 1
                    vis[j] = v2
                    break
                j, v1[0] = v1[0][0], v2[0]

        ans.append(val)

    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	t=II()
	for _ in range(t):
		n=II()
		L=[]
		R=[]
		ans=0
		for _ in range(n):
			k,l,r=MI()
			if l>=r:
				ans+=r
				L.append((k,l-r))
			else:
				ans+=l
				R.append((n-k,r-l))
		L.sort()
		R.sort()
		#print(L,R)

		Q=[]
		heapq.heapify(Q)

		for k,v in L:
			ans+=v
			heapq.heappush(Q,(k,v))
			if len(Q)>k:
				_,vv=heapq.heappop()
				ans-=vv

		Q=[]
		heapq.heapify(Q)

		for k,v in R:
			ans+=v
			heapq.heappush(Q,-v)
			if len(Q)>k:
				vv=heapq.heappop(Q)
				ans+=vv
		print(ans)


























if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	t=II()
	for _ in range(t):
		n=II()
		L=[]
		R=[]
		ans=0
		for _ in range(n):
			k,l,r=MI()
			if l>=r:
				ans+=r
				L.append((k,l-r))
			else:
				ans+=l
				R.append((n-k,r-l))
		L.sort()
		R.sort()
		#print(L,R)

		Q=[]
		heapq.heapify(Q)

		for k,v in L:
			ans+=v
			heapq.heappush(Q,(k,v))
			if len(Q)>k:
				_,vv=heapq.heappop()
				ans-=vv

		Q=[]
		heapq.heapify(Q)

		for k,v in R:
			ans+=v
			heapq.heappush(Q,(-v,k))
			if len(Q)>k:
				vv,_=heapq.heappop(Q)
				ans+=vv
		print(ans)


























if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	t=II()
	for _ in range(t):
		n=II()
		L=[]
		R=[]
		ans=0
		for _ in range(n):
			k,l,r=MI()
			if l>=r:
				ans+=r
				L.append((k,l-r))
			else:
				ans+=l
				R.append((n-k,r-l))
		L.sort()
		R.sort()
		#print(L,R)

		Q=[]
		heapq.heapify(Q)

		for k,v in L:
			ans+=v
			heapq.heappush(Q,(k,v))
			if len(Q)>k:
				_,vv=heapq.heappop()
				ans-=vv

		Q=[]
		heapq.heapify(Q)

		for k,v in R:
			ans+=v
			heapq.heappush(Q,(k,v))
			if len(Q)>k:
				_,vv=heapq.heappop(Q)
				ans-=vv
		print(ans)


























if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	t=II()
	for _ in range(t):
		n=II()
		L=[]
		R=[]
		ans=0
		for _ in range(n):
			k,l,r=MI()
			if l>=r:
				ans+=r
				L.append((k,l-r))
				L.sort()
			else:
				ans+=l
				R.append((n-k,r-l))
				R.sort()
		#print(L,R)

		Q=[]
		heapq.heapify(Q)

		for k,v in L:
			ans+=v
			heapq.heappush(Q,(k,v))
			if len(Q)>k:
				_,vv=heapq.heappop()
				ans-=vv

		Q=[]
		heapq.heapify(Q)

		for k,v in R:
			ans+=v
			heapq.heappush(Q,(k,v))
			if len(Q)>k:
				_,vv=heapq.heappop(Q)
				ans-=vv
		print(ans)


























if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import heapq  
def priority(klr):
    return abs(klr[1]-klr[2])
              
def process(KLR):
    ans = 0   
    q = []    
    for klr in KLR:
        pr = priority(klr)
        if klr[0] < len(q) and q[0][0] < pr:
            tmp = heapq.heappop(q)
            ans += min(tmp[1], tmp[2])
        if klr[0] >= len(q):
            heapq.heappush(q, (pr, klr))
    for pr, klr in q:
        ans += max(klr[1], klr[2])
    return ans
              
              
def solve():  
    N = int(input())
    KLR = []  
    for _ in range(N):
        klr = list(map(int, input().split()))
        klr[0] -= 1 # convert to 0-based index to avoid confusion                                                                                                                                           
        KLR.append(klr)
    ans = 0   
    KLR_L = []
    KLR_R = []
    for klr in KLR:
        if klr[1] > klr[2]:
            KLR_L.append(klr)
        elif klr[1] < klr[2]:
            klr[0] = N-1-klr[0]-1
            if klr[0] < 0:
                ans += min(klr[1], klr[2])
            else:
                KLR_R.append(klr)
        else: 
            ans += klr[1]
    KLR_L.sort(key=lambda klr: klr[0])
    KLR_R.sort(key=lambda klr: klr[0])
    ans += process(KLR_L)
    ans += process(KLR_R)
    print(ans)
              
T = int(input())
              
for _ in range(T):
    solve()