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
import math
from collections import deque
import heapq as hq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    T = NI()
    for _ in range(T):
        N = NI()
        camels = [NLI() 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] # LとRの低いほうを加算
            else:
                camels_R[N - camel[0]].append(camel[2] - camel[1])
                base += camel[1] # LとRの低いほうを加算
        ans = 0
        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_L[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop()
        if heap_camels:
            ans += sum(heap_camels)

        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()
        if heap_camels:
            ans += sum(heap_camels)
        print(ans + base)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import heapq as hq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    T = NI()
    A = []
    for _ in range(T):
        N = NI()
        camels = [NLI() 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] # LとRの低いほうを加算
            else:
                camels_R[N - camel[0]].append(camel[2] - camel[1])
                base += camel[1] # LとRの低いほうを加算
        ans = 0
        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_L[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop()
        ans += sum(heap_camels)

        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()
        ans += sum(heap_camels)
        print(ans + base)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

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 [1]:
    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: Runtime Error

Solution code:
T = int(input())
Kli = [[] for _ in range(T)]
Lli = [[] for _ in range(T)]
Rli = [[] for _ in range(T)]
Nli = [[] for _ in range(T)]
for t in range(T):
    N = int(input())
    for n in range(N):
        K, L, R = map(int, input().split())
        Rli[t].append(R)
        Nli[t].append([K, L-R])
ansli = [[0 for _ in range(N+1)] for _ in range(T)]
for t in range(T):
    Nli[t].sort(key=lambda x: x[1], reverse = True)
    for i in range(len(Nli[t])):
        if Nli[t][i][1] < 0:
            for j in range(1,len(ansli[t])):
                if ansli[t][-j] == 0:
                    if len(ansli[t])-j > Nli[t][i][0]:
                        break
                    else:
                        ansli[t][-j] = Nli[t][i][1]
                        break
        elif ansli[t][Nli[t][i][0]] == 0:
            ansli[t][Nli[t][i][0]] = Nli[t][i][1]
        else:
            for k in range(1,Nli[t][i][0]):
                if ansli[t][Nli[t][i][0]-k] == 0:
                    ansli[t][Nli[t][i][0]-k] = Nli[t][i][1]
                    break
for t in range(T):
    print(sum(ansli[t])+sum(Rli[t]))

Submission status: Runtime Error

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)
  Mdic = DD(list)
  Udic = DD(list)
  Mcount = 0
  Ucount = 0
  ans = 0
  for K,L,R in data:
    if L>=R:
      Mdic[K-1].append(L-R)
      ans += R
      Mcount += 1
    else:
      Udic[N-1-K].append(R-L)
      ans += L
      Ucount += 1
  q = []
  for i in range(N):
    for v in Mdic[i]:
      ans += v
      heapq.heappush(q,v)
    while len(q)>i+1:
      ans -= heapq.pop(q)
  q = []
  for i in range(N):
    for v in Udic[i]:
      ans += v
      heapq.heappush(q,v)
    while len(q)>i+1:
      ans -= heapq.pop(q)
  print(ans)

Submission status: Runtime Error

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

import heapq
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    head=[]
    tail=[]
    for k,l,r in arr:
        if l>=r or k==n:
            head.append((k,l,r))
        else:
            tail.append((k,l,r))
    head=sorted(head,key=lambda x:x[0])
    q=[]
    cnt=0
    ans=[]
    for k,l,r in head:
        heapq.heappush(q,(l-r,l))
        cnt+=1
        while cnt>k:
            tmp,val=heapq.heappop(q)
            ans.append((tmp,val-tmp))
            cnt-=1
    ans+=list(q)
    cnt=len(ans)
    tail2=[]
    for k,l,r in tail:
        if k<=cnt:
            ans.append((l-r,r))
        else:
            tail2.append((k,l,r))
    tail2=sorted(tail2,reverse=True,key=lambda x:x[0])
    q2=[]
    cnt2=0
    for k,l,r in tail2:
        heapq.heappush(q2,(r-l,r))
        cnt2+=1
        while cnt2>(n-k+1):
            tmp,val=heapq.heappop(q2)
            ans.append((tmp,val-tmp))
            cnt-=1
    ans+=list(q2)
    ret=0
    for _,val in ans:
        ret+=val
    print(ret)

Submission status: Runtime Error

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

import heapq
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    head=[]
    tail=[]
    for k,l,r in arr:
        if l>=r or k==n:
            head.append((k,l,r))
        else:
            tail.append((k,l,r))
    head=sorted(head,key=lambda x:x[0])
    q=[]
    cnt=0
    ans=[]
    for k,l,r in head:
        heapq.heappush(q,(l-r,l))
        cnt+=1
        while cnt>k:
            tmp,val=heapq.heappop()
            ans.append((tmp,val-tmp))
            cnt-=1
    ans+=list(q)
    cnt=len(ans)
    tail2=[]
    for k,l,r in tail:
        if k<=cnt:
            ans.append((l-r,r))
        else:
            tail2.append((k,l,r))
    tail2=sorted(tail2,reverse=True,key=lambda x:x[0])
    q2=[]
    cnt2=0
    for k,l,r in tail2:
        heapq.heappush(q2,(r-l,r))
        cnt2+=1
        while cnt2>(n-k+1):
            tmp,val=heapq.heappop()
            ans.append((tmp,val-tmp))
            cnt-=1
    ans+=list(q2)
    ret=0
    for _,val in ans:
        ret+=val
    print(ret)

Submission status: Runtime Error

Solution code:
t = int(input())

for i in range(t):
  n = int(input())  # nは入力回数
  arr = [list(map(int, input().split())) for _ in range(n)]
  
  lb = [i for i in arr if i[1] > i[2]]
  rb = [i for i in arr if i[1] < i[2]]
  lb.sort(key = lambda x: x[1], reverse = True)
  rb.sort(key = lambda x: x[2])
  
  apparr = rb + lb
  print(sum(apparr))

Submission status: Runtime Error

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

N=int(input().rstrip('\n'))
for i in range(N):
  T=int(input().rstrip('\n'))
  rs_p=[]
  rs_n=[]
  rs_a=[]
  dif = []
  ans=[0]*T
  for y in range(T):
    rs = tuple(int(x) for x in input().rstrip('\n').split())
    rs_a.append(rs)
    dif.append(abs(rs[1]-rs[2]))
    if rs[1]>rs[2]:
      rs_p.append(y)
    else:
      rs_n.append(y)
  for x in range(T):
    p = [i for i, x in enumerate(dif) if x == max(dif)]
    q = p[0]
    rn=rs_a[q]
    if q in rs_p:
      for i in range(rn[0]-1,0,-1):
        if ans[i]==0:
          ans[i]=rn[1]
          break
    else:
      for i in range(T,0,-1):
        if ans[i]==0:
          ans[i]=rn[2]
          break
  print(sum(ans))

Submission status: Runtime Error

Solution code:
def solve():
  T = int(input())
  ans = [0]*T
  for t in range(T):
    N = int(input())
    left = []
    right = []
    for i in range(N):
      k,l,r = map(int, input().split())
      if k==N:
        ans[t] += l
      elif l>r:
        left.append([k,l-r])
        ans[t] += r
      elif l<r:
        right.append([k,r-l])
        ans[t] += l
      else:
        ans[t] += l
    left.sort(key = lambda x:(-x[0],-x[1]))
    right.sort(key = lambda x:(x[0],-x[1]))
    now = left[0][0]
    ans[t] += left[0][1]
    for i in range(1,len(left)):
      while left[i][0]>=now:
        left[i][0] -= 1
      ans[t] += left[i][1]
      now -= 1
      if now==0:
        break
    now = right[0][1]
    for i in range(1,len(left)):
      while right[i][0]<=now:
        right[i][0] -= 1
      ans[t] += right[i][1]
      now -= 1
      if now==0:
        break
  return ans
print(*solve(),sep='\n')

Submission status: Runtime Error

Solution code:
from operator import itemgetter
from heapq import heappush, heappop

T = int(input())

def solve():
	n = int(input())
	pos = []
	diff = []
	value = []

	pos = []
	neg = []	
	a = []

	for i in range(n):
		x, y, z = map(int, input().split())
	
		if y > z: 
			pos.append((x, y - z, i))	
		else:
			neg.append((x, z - y, i))

		a.append((x, y, z))

	pos = sorted(pos, key = lambda x:[n - x[0], x[1]])
	neg = sorted(neg, key = lambda x:[x[0], x[1]])

	position = len(pos) - 1
	idx = 0

	heap = []

	pos_good = []


	while position >= 0:
		while pos[idx][0] == position and idx < len(pos):
			heappush((-pos[idx][1], pos[idx][2]))
			idx += 1

		best = heappop(heap)
		pos_good.append(best[2])
		position -= 1

	heap = []
	neg_good = []

	idx = 0
	position = len(pos)

	while position < n:
		while neg[idx][0] == position and idx < len(neg):
			heappush((-neg[idx][1], neg[idx][2]))
			idx += 1

		best = heappop(heap)
		neg_good.append(best[2])
		position += 1

	pos_good = set(pos_good)
	neg_good = set(neg_good)

	result = 0

	for i in range(n):
		x, y, z = a[i]
		if y > z:
			if i in pos_good:
				result += y

			else:
				result += z

		else:
			if i in neg_good:
				result += z
			else:
				result += y

	print(result)

for t in range(T):
	solve()

Submission status: Runtime Error

Solution code:
import heapq

def main2(l, n):
    ans = 0
    length = len(l[0])
    lis = heapq.heapify(l[0])
    while length > 1:
        length -= 1
        ans += heapq.heappop(lis)
    for i in range(1, n):
        length += len(l[i])
        for j in l[i]:
            heapq.heappush(lis, j)
        while length > i + 1:
            length -= 1
            ans += heapq.heappop(lis)
    return ans

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    t = int(input())

    answer = []
    for _ in range(t):
        n = int(input())
        ans = 0
        l = [[] for _ in range(n)]
        r = [[] for _ in range(n)]
        for _ in range(n):
            i, j, k = map(int, input().split())
            if j > k:
                ans += j
                l[i-1].append(j-k)
            if j < k:
                ans += k
                r[n-i].append(k-j)
            ans -= main2(l, n) + main2(r, n)
            answer.append(ans)

    for i in answer:
        print(i)

main()

Submission status: Runtime Error

Solution code:
def main()import sys
import heapq
input = sys.stdin.readline

def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        ans = 0
        judge_f = [[] for _ in range(n)]
        judge_b = [[] for _ in range(n)]
        for j in range(n):
            k, l, r = map(int, input().split())
            ans += min(l, r)
            if r < l:
                judge_b[k-1].append(l-r)
            elif l < r:
                if k != n:
                    judge_f[k].append(r-l)
        plus = [0]*n
        minus = [0]*n
        key = []
        heapq.heapify(key)
        for j in range(n):
            if judge_b[j]:
                for v in judge_b[j]:
                    heapq.heappush(key, -v)
            if key:
                minus[j] = -heapq.heappop(key)
        key = []
        heapq.heapify(key)
        for j in range(n-1, -1, -1):
            if judge_f[j]:
                for v in judge_f[j]:
                    heapq.heappush(key, -v)
            if key:
                plus[j] = -heapq.heappop(key)
        for i in range(1, n):
            plus[i] += plus[i-1]
            minus[n-i-1] += minus[n-i]
        
        count = 0
        for i in range(n):
            if count < plus[i]+minus[i]:
                count = plus[i]+minus[i]
        print(ans+count)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")
def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [INF] * (2 * self.N0)

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = min(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の最小値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = INF
		while L < R:
			if R & 1:
				R -= 1
				m = min(m, self.data[R - 1])
			if L & 1:
				m = min(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

class SegmentTreeMAX(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [-INF] * (2 * self.N0)

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = max(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の最小値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = -INF
		while L < R:
			if R & 1:
				R -= 1
				m = max(m, self.data[R - 1])
			if L & 1:
				m = max(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m


#処理内容
def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		Seg = SegmentTree(N)
		SegMAX = SegmentTreeMAX(N)
		#セグ木をindexで初期化
		for i in range(N):
			Seg.update(i, i)
			SegMAX.update(i, i)

		ans = 0
		Lis = []
		for i in range(N):
			K, L, R = getlist()
			ans += R
			dif = L - R
			Lis.append([abs(dif), dif, K - 1])

		Lis.sort()
		for i in range(N):
			ab, diff, ind = Lis[-1 - i]
			# 絶対にK番目以内になる場合
			if diff >= 0:
				if ind >= N - 1:
					ans += diff
				else:
					segInd = SegMAX.query(0, ind)
					if segInd == INF:
						pass
					else:
						ans += diff
						SegMAX.update(segInd, -INF)
			else:
				if ind >= N - 1:
					ans += diff
				# K番目に入るかの判定
				else:
					segInd = Seg.query(ind + 1, N - 1)
					if segInd == INF:
						ans += diff
					else:
						Seg.update(segInd, INF)

		print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")
def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [INF] * (2 * self.N0)

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = min(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の最小値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = INF
		while L < R:
			if R & 1:
				R -= 1
				m = min(m, self.data[R - 1])
			if L & 1:
				m = min(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

class SegmentTreeMAX(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [-INF] * (2 * self.N0)

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = max(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の最小値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = -INF
		while L < R:
			if R & 1:
				R -= 1
				m = max(m, self.data[R - 1])
			if L & 1:
				m = max(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m


#処理内容
def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		Seg = SegmentTree(N)
		SegMAX = SegmentTreeMAX(N)
		#セグ木をindexで初期化
		for i in range(N):
			Seg.update(i, i)
			SegMAX.update(i, i)

		ans = 0
		Lis = []
		for i in range(N):
			K, L, R = getlist()
			ans += R
			dif = L - R
			Lis.append([abs(dif), dif, K - 1])

		Lis.sort()
		for i in range(N):
			ab, diff, ind = Lis[-1 - i]
			# 絶対にK番目以内になる場合
			if diff >= 0:
				if ind >= N - 1:
					ans += diff
				else:
					segInd = SegMAX.query(0, ind)
					if segInd == INF:
						pass
					else:
						ans += diff
						SegMAX.update(segInd, -INF)
			else:
				if ind >= N - 1:
					ans += diff
				# K番目に入るかの判定
				else:
					segInd = Seg.query(ind + 1, N - 1)
					if segInd == -INF:
						ans += diff
					else:
						Seg.update(segInd, INF)

		print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")
def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [INF] * (2 * self.N0)

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = min(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の最小値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = INF
		while L < R:
			if R & 1:
				R -= 1
				m = min(m, self.data[R - 1])
			if L & 1:
				m = min(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

class SegmentTreeMAX(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [-INF] * (2 * self.N0)

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = max(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の最小値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = -INF
		while L < R:
			if R & 1:
				R -= 1
				m = max(m, self.data[R - 1])
			if L & 1:
				m = max(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m


#処理内容
def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		Seg = SegmentTree(N)
		SegMAX = SegmentTreeMAX(N)
		#セグ木をindexで初期化
		for i in range(N):
			Seg.update(i, i)
			SegMAX.update(i, i)

		ans = 0
		Lis = []
		for i in range(N):
			K, L, R = getlist()
			ans += R
			dif = L - R
			Lis.append([abs(dif), dif, K - 1])

		Lis.sort()
		for i in range(N):
			ab, diff, ind = Lis[-1 - i]
			# 絶対にK番目以内になる場合
			if diff >= 0:
				if ind >= N - 1:
					ans += diff
				else:
					segInd = SegMAX.query(0, ind)
					if segInd == INF:
						pass
					else:
						ans += diff
						SegMAX.update(segInd, -INF)
			else:
				if ind >= N - 1:
					ans += diff
				# K番目に入るかの判定
				else:
					segInd = Seg.query(ind + 1, N - 1)
					if segInd == -INF:
						ans += diff
					else:
						SegMAX.update(segInd, -INF)

		print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y))

for ansi in reversed(ans):
    print(ansi)

Submission status: Runtime Error

Solution code:
for _ in range(int(input())):
    c=0
	for i in range(1,int(input())+1):
    	k,l,r=map(int,input().split())
        if i==1 and k==1:
               c+=r
        elif i<=k:
        	c+=r
        else:
        	c+=l
	print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
left=[]
right=[]
for i in range(N):
  k,l,r=map(int,input().split())
  if l >= r:left.append((i,k,l,r,l-r))
  else:right.append((i,k,l,r,r-l))
left = sorted(left, key=lambda x:x[4])
left = sorted(left, key=lambda x:x[1], reverse=True)
right = sorted(right, key=lambda x:x[4])
right = sorted(right, key=lambda x:x[1], reverse=True)

sum_ = 0
left_cnt, right_cnt = 0,0
while 1:
  try:
    idx,k,l,r,_ = left.pop()
    if left_cnt<k:
      sum_ += l
      left_cnt += 1
    else:
      sum_ += r
      left_cnt += 1
  except:
    pass
  try:
    idx,k,l,r,_ = right.pop()
    if N-right_cnt>k:
      sum_ += r
      right_cnt += 1
    else:
      sum_ += l
      right_cnt += 1
  except:
    pass
  if left_cnt+right_cnt==N:break

print(sum_)

Submission status: Runtime Error

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))
import heapq


t = readint()
ans = []

for _ in range(t):
    n = readint()
    a = []
    b = []
    score = 0
    for i in range(n):
        k,l,r = readints()
        if k==n:
            score += l
        elif l>r:
            a.append([k,l,r])
            score += l
        elif l<r:
            b.append([n-k,l,r])
            score += r
        else:
            score += r
    a.sort()
    b.sort()
    left = []
    right = []
    heapq.heapify(left)
    heapq.heapify(right)
    lenl = 0
    lenr = 0
    for k,l,r in a:
        if k>lenl:
            heapq.heappush(left,[l,r])
            lenl += 1
        else:
            if l-r>left[0][0]:
                y = heapq.heappop(left)
                heapq.heappush(left,[l-r,l,r])
                score -= y[1]
                score += y[2]
            else:
                score -= l
                score += r
    for k,l,r in b:
        if k>lenr:
            heapq.heappush(right,[r-l,l,r])
            lenr += 1
        else:
            if r-l>right[0][0]:
                y = heapq.heappop(right)
                heapq.heappush(right,[r-l,l,r])
                score -= y[2]
                score += y[1]
            else:
                score -= r
                score += l
    ans.append(score)
printrows(ans)