Problem:


Score : 500 points

Problem Statement

We have N camels numbered 1,2,\ldots,N.
Snuke has decided to make them line up in a row.

The happiness of Camel i will be L_i if it is among the K_i frontmost camels, and R_i otherwise.

Snuke wants to maximize the total happiness of the camels. Find the maximum possible total happiness of the camel.

Solve this problem for each of the T test cases given.

Constraints

All values in input are integers.

1 \leq T \leq 10^5

1 \leq N \leq 2 \times 10^{5}

1 \leq K_i \leq N

1 \leq L_i, R_i \leq 10^9

The sum of values of N in each input file is at most 2 \times 10^5.

Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is given in the following format:

N
K_1 L_1 R_1
\vdots
K_N L_N R_N

Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Sample Input 1

3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34

Sample Output 1

25
221
1354

In the first test case, it is optimal to line up the camels in the order 2, 1.

Camel 1 is not the frontmost camel, so its happiness will be 10.

Camel 2 is among the two frontmost camels, so its happiness will be 15.

In the second test case, it is optimal to line up the camels in the order 2, 1, 3.

Camel 1 is among the two frontmost camels, so its happiness will be 93.

Camel 2 is the frontmost camel, so its happiness will be 71.

Camel 3 is among the three frontmost camels, so its happiness will be 57.



Sample input:
3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34


Sample output:
25
221
1354

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import heapq

def _solve(N, _list):
    n = len(_list)
    # Kの昇順
    _list.sort(key=lambda x: x[0])
    
    # まず、最低限得られるうれしさを求める
    base_score = sum([x[2] for x in _list])

    ni = 0
    S = []
    for j in range(N+1):
        # Ki = j であるラクダをSに追加
        while ni < n and _list[ni][0] == j:
            _, L, R = _list[ni]
            heapq.heappush(S, L - R)
            ni += 1
        # len(S) > j である場合、増えるうれしさの小さいものを削除する
        while len(S) > j:
            heapq.heappop(S)

    return base_score + sum(S)# + sum([x[1]-x[2] for x in _list[ni:]])

def solve(N, KLR):
    BigL = [] # L の方が大きいやつ
    BigR = [] # R の方が大きいやつ

    for i in range(N):
        K, L, R = KLR[3*i], KLR[3*i+1], KLR[3*i+2]
        # L の方が大きいやつと、 Rの方が大きいやつに分けて考える
        if L < R:
            # R の方が大きいやつは、LとRを逆転させて、
            # Lの方が大きいやつと同じように考えられるようにする
            BigR.append((N-K, R, L))
        else:
            # 番号が0から始まるようにする
            BigL.append((K, L, R))

    return _solve(N, BigL) + _solve(N, BigR)
        
def main():
    T, *_all = map(int, read().split())
    n = 0

    ans = []
    for _ in range(T):
        N = _all[n]
        KLR = _all[n+1:n+1+3*N]
        ans.append(solve(N, KLR))
        n += 1 + 3*N

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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.heappop(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.heappop(q)
  print(ans)

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

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=map(int,i().split());x+=[(k,l,r)]*(l>r);y+=[(n-k,r,l)]*(l<=r)
 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)

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=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 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)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

t = onem()

for _ in range(t):
	n = onem()
	L = []
	R = []
	ans = 0
	for i in range(n):
		k,l,r = m()
		if l >= r:
			L.append([k,l-r])
			ans += r
		else:
			R.append([n-k + 1,r-l])
			ans += l
	L.sort()
	R.sort()

	po = []
	ii = 0
	for i in range(n):
		while ii < len(L):
			if L[ii][0] == i+1:
				hq.heappush(po,L[ii][1])
				ii += 1
			else:
				break
		while len(po) > i+1:
			hq.heappop(po)
	ans += sum(po)
	po = []
	ii = 0
	for i in range(n):
		while ii < len(R):
			if R[ii][0] == i+1:
				hq.heappush(po,R[ii][1])
				ii += 1
			else:
				break
		while len(po) > i:
			hq.heappop(po)
	ans += sum(po)
	print(ans)

Submission status: Accepted

Solution code:
import heapq
t = int(input())
for _ in range(t):
    n = int(input())
    L, R = [], []
    N = [[] for j in range(n)]
    P = [[] for j in range(n + 1)]
    for i in range(n):
        k, l, r = map(int, input().split())
        if l - r > 0:
            N[k - 1].append(i)
        else:
            P[k].append(i)
        L.append(l)
        R.append(r)
    ans = sum([min(L[i], R[i]) for i in range(n)])
    S, T = [], []
    for j in range(n):
        for i in N[j]:
            heapq.heappush(S, L[i] - R[i])
        for i in P[n - 1 - j]:
            heapq.heappush(T, R[i] - L[i])
        while len(S) > j + 1:
            heapq.heappop(S)
        while len(T) > j + 1:
            heapq.heappop(T)
    print(ans + sum(S) + sum(T))

Submission status: Accepted

Solution code:
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    t = int(ipt())
    for _ in range(t):
        n = int(ipt())
        camp = [[] for i in range(n+1)]
        camm = [[] for i in range(n+1)]
        ans = 0
        pn = 0
        for i in range(n):
            k,l,r = map(int,ipt().split())
            ans += min(r,l)
            if l >= r:
                camp[k].append(l-r)
                pn += 1
            else:
                camm[k].append(r-l)

        hq = []
        for i in range(1,n+1):
            for j in camp[i]:
                hpq.heappush(hq,j)
            t = len(hq)-i
            for j in range(t):
                hpq.heappop(hq)
        for i in hq:
            ans += i
            
        hq = []
        for i in range(n):
            for j in camm[n-i]:
                hpq.heappush(hq,j)
            t = len(hq)-i
            for j in range(t):
                hpq.heappop(hq)
        for i in hq:
            ans += i

        print(ans)



    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
t = int(input())
for i in range(t):
    n = int(input())
    ans = 0
    cl,cr = 0,0
    lisl = []
    lisr = []
    rs = 0
    ls = 0
    for i in range(n):
        k,l,r = map(int,input().split())
        a = r-l
        s = (l>r)
        if a<0:
            lisl.append([k,l,r,-a,s])
            rs += r
        else:
            lisr.append([k,l,r,a,s])
            ls += l
    lisl.sort(key=lambda x: x[0])
    lisr.sort(key=lambda x: x[0],reverse=1)
    h = []
    cntl = 0
    cntr = 0
    for i in lisl:
        heapq.heappush(h,i[3])
        cntl += 1
        if cntl > i[0]:
            heapq.heappop(h)
            cntl -= 1
    hr = []
    for i in lisr:
        heapq.heappush(hr,i[3])
        cntr += 1
        if cntr > n-i[0]:
            heapq.heappop(hr)
            cntr -= 1
    print(rs+sum(h)+ls+sum(hr))

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=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 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)

Submission status: Accepted

Solution code:
import heapq
t = int(input())
for i in range(t):
    n = int(input())
    ans = 0
    cl,cr = 0,0
    lisl = []
    lisr = []
    rs = 0
    ls = 0
    for i in range(n):
        k,l,r = map(int,input().split())
        a = r-l
        s = (l>r)
        if a<0:
            lisl.append([k,l,r,-a,s])
            rs += r
        else:
            lisr.append([k,l,r,a,s])
            ls += l
    # lisl.sort(key=lambda x: x[3])
    lisl.sort(key=lambda x: x[0])
    # lisr.sort(key=lambda x: x[3])
    lisr.sort(key=lambda x: x[0],reverse=1)
    # print(lis)
    h = []
    cntl = 0
    cntr = 0
    # print(lisl)
    # print(lisr)
    for i in lisl:
        heapq.heappush(h,i[3])
        cntl += 1
        if cntl > i[0]:
            heapq.heappop(h)
            cntl -= 1
    # print(h)
    hr = []
    for i in lisr:
        heapq.heappush(hr,i[3])
        cntr += 1
        if cntr > n-i[0]:
            heapq.heappop(hr)
            cntr -= 1
    # print(hr)
    # heapq.heappop(hr)
    # print(hr)
    print(rs+sum(h)+ls+sum(hr))

Submission status: Accepted

Solution code:
from heapq import*
i=input
def f(x):
 x.sort();s,n,*h=0,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]
 return s+sum(r for*_,r in x+h)
for _ in'_'*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),
 print(f(x)+f(y))

Submission status: Accepted

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


def simulate(camels):
    camels.sort(key=itemgetter(0))
    queue = []
    ans = 0
    for k, l, r in camels:
        ans += l
        if len(queue) < k:
            # ok
            heappush(queue, l - r)
        else:
            heappush(queue, l - r)
            d = heappop(queue)
            ans -= d
    return ans


def solve():
    n = int(input())
    camels = [tuple(map(int, input().split())) for _ in range(n)]

    ans = 0
    camels_l = []
    camels_r = []
    for k, l, r in camels:
        if k == n or l == r:
            ans += l
        elif l > r:
            camels_l.append((k, l, r))
        else:
            # r > l
            camels_r.append((n - k, r, l))

    ans += simulate(camels_l)
    ans += simulate(camels_r)

    print(ans)


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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


t = int(input())
ANS = [None]*t
from collections import defaultdict
from heapq import heappop as hpp, heappush as hp
for iii in range(t):
    n = int(input())
    d1 = defaultdict(list)
    d0 = defaultdict(list)
    lr = [None]*n
    for i in range(n):
        k,l,r = list(map(int, input().split()))
        lr[i] = (l,r)
        if l-r>=0:
            d1[k].append((l-r, i))
        else:
            d0[k].append((r-l, i))
            
    sl = set()
    sr = set()
    h = []
    for i in range(1,n+1):
        if i not in d1:
            continue
        for item in d1[i]:
            hp(h, item)
        while i<len(h):
            *_,ii = hpp(h)
            sr.add(ii)
    for *_,i in h:
        sl.add(i)
    h = []
    for i in range(n, 0, -1):
        if i not in d0:
            continue
        for item in d0[i]:
            hp(h,item)
        while (n-i)<len(h):
            *_,ii = hpp(h)
            sl.add(ii)
    for *_,i in h:
        sr.add(i)
    ans = 0
#     print(lr0, lr1, sl, sr)
    for i in sl:
        ans += lr[i][0]
    for i in sr:
        ans += lr[i][1]
    ANS[iii] = ans
write("\n".join(map(str, ANS)))

Submission status: Accepted

Solution code:
import sys
import heapq


input = sys.stdin.readline

T = int(input())

def solve():
    N = int(input())
    ls = []
    rs = []
    heapq.heapify(ls)
    heapq.heapify(rs)
    for _ in range(N):
        k, l, r = map(int, input().split())
        if l - r >= 0:
            heapq.heappush(ls, (k, l, r))
        else:
            heapq.heappush(rs, (N-k, l, r))
    ans = 0
    ls_l = []
    heapq.heapify(ls_l)
    while len(ls) != 0:
        k, l, r = heapq.heappop(ls)
        heapq.heappush(ls_l, (l-r))
        ans += r
        while len(ls_l) > k:
            heapq.heappop(ls_l)
    rs_r = []
    heapq.heapify(rs_r)
    while len(rs) != 0:
        k, l, r = heapq.heappop(rs)
        heapq.heappush(rs_r, (r-l))
        ans += l
        while len(rs_r) > k:
            heapq.heappop(rs_r)
    while len(ls_l) != 0:
        ans += heapq.heappop(ls_l)
    while len(rs_r) != 0:
        ans += heapq.heappop(rs_r)
    print(ans)


for _ in range(T):
    solve()

Submission status: Accepted

Solution code:
import sys
import heapq


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def reward(n, d):
    s = []
    for i in range(n):
        for item in d.get(i, []):
            heapq.heappush(s, item)
        for _ in range(len(s), i+1, -1):
            _ = heapq.heappop(s)
    return sum(s)


def test():
    n = _i()
    ll, rr = {}, {}
    mn = ln = rn = 0
    for i in range(n):
        k, l, r = _ia()
        mn += min(l, r)
        if l >= r:
            ll[k-1] = ll.get(k-1, []) + [l-r]
            ln += 1
        else:
            rr[n-k-1] = rr.get(n-k-1, []) + [r-l]
            rn += 1

    return mn + reward(n, ll) + reward(n, rr)


def main():
    t = _i()
    ret = [test() for _ in range(t)]
    return "\n".join(map(str, ret))


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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)]
    q=[]
    ans=0
    camels1=[[] for _ in range(n+1)]
    camels2=[[] for _ in range(n+1)]
    for k,l,r in arr:
        if l>=r:
            camels1[k].append((l,r))
        else:
            camels2[k].append((l,r))
    for i in range(1,n+1):
        for l,r in camels1[i]:
            heapq.heappush(q,(l-r,l,r))
        while len(q)>i:
            _,_,r=heapq.heappop(q)
            ans+=r
    while len(q)!=0:
        _,l,_=heapq.heappop(q)
        ans+=l
    for i in range(n,0,-1):
        for l,r in camels2[i]:
            heapq.heappush(q,(r-l,l,r))
        while len(q)>(n-i):
            _,l,_=heapq.heappop(q)
            ans+=l
    while len(q)!=0:
        _,_,r=heapq.heappop(q)
        ans+=r
    print(ans)

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

for _ in range(II()):
    n=II()
    ff=[]
    bb=[]
    ans=0
    for _ in range(n):
        k,l,r=MI()
        if l>r:ff.append((k,l,r))
        elif l<r:bb.append((n-k,l,r))
        else:ans+=r

    ff.sort()
    hp=[]
    for i,(k,l,r) in enumerate(ff):
        heappush(hp,l-r)
        ans+=l
        if i+1<len(ff) and ff[i+1][0]==k:continue
        while len(hp)>k:
            d=heappop(hp)
            ans-=d

    bb.sort()
    hp = []
    for i, (k, l, r) in enumerate(bb):
        heappush(hp, r-l)
        ans += r
        if i + 1 < len(bb) and bb[i + 1][0] == k: continue
        while len(hp) > k:
            d = heappop(hp)
            ans -= d

    print(ans)

Submission status: Accepted

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)]
    q=[]
    ans=0
    camels1=[[] for _ in range(n+1)]
    camels2=[[] for _ in range(n+1)]
    for k,l,r in arr:
        ans+=min(l,r)
        if l>=r:
            camels1[k].append((l,r))
        else:
            camels2[k].append((l,r))
    for i in range(1,n+1):
        for l,r in camels1[i]:
            heapq.heappush(q,l-r)
        while len(q)>i:
            heapq.heappop(q)
    while len(q)!=0:
        ans+=heapq.heappop(q)
    for i in range(n,0,-1):
        for l,r in camels2[i]:
            heapq.heappush(q,r-l)
        while len(q)>(n-i):
            heapq.heappop(q)
    while len(q)!=0:
        ans+=heapq.heappop(q)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

t = int(input())
for i in range(t):
    n = int(input())
    a1 = []
    a2 = []
    ans = 0
    for j in range(n):
        k, l, r = map(int, input().split())
        if l > r:
            a1.append([l - r, k])
            ans += l
        elif l < r:
            a2.append([r - l, n - k])
            ans += r
        else:
            ans += l
    a1.sort(key = lambda x: x[1])
    a2.sort(key = lambda x: x[1])
    num = 1
    num2 = 0
    num3 = 0
    queue = []
    heapq.heapify(queue)
    while num <= n:
        if num2 == len(a1):
            break
        else:
            while a1[num2][1] == num:
                heapq.heappush(queue, a1[num2])
                num2 += 1
                num3 += 1
                if num2 == len(a1):
                    break
            while num3 > num:
                temp = heapq.heappop(queue)
                ans -= temp[0]
                num3 -= 1
            else:
                num += 1
    num = 0
    num2 = 0
    num3 = 0
    queue = []
    heapq.heapify(queue)
    while num <= n:
        if num2 == len(a2):
            break
        else:
            while a2[num2][1] == num:
                heapq.heappush(queue, a2[num2])
                num2 += 1
                num3 += 1
                if num2 == len(a2):
                    break
            while num3 > num:
                temp = heapq.heappop(queue)
                ans -= temp[0]
                num3 -= 1
            else:
                num += 1
    print(ans)

Submission status: Accepted

Solution code:
from heapq import*
s=sorted
def f(x):
 s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for*_,r in x+h)
z=open(0).read().split()
i=1
while i<len(z):
 n,x,*y=int(z[i]),[];i+=1
 for k,l,r in zip(*[map(int,z[i:i+n*3])]*3):
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print(f(s(x))+f(s(y)));i+=n*3

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  from heapq import heapify,heappop,heappush
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    ans = 0
    for K,L,R in KLR:
      x = L - R
      if x==0:
        ans += L
      elif x>0:
        left.append([K,L,R])
        ans += R
      else:
        right.append([K+1,L,R])
        ans += L

    left = sorted(left)
    right = sorted(right,reverse=True)
      
    S = []
    heapify(S)
    x = 1
    i = 0
    length = len(left)
    while x<=N:
      while i<length:
        klr = left[i]
        if klr[0]==x:
          heappush(S,klr[1]-klr[2])
          i += 1
          
        else:
          break
      
      y = len(S) - x
      if y<=0:
        x += 1
        continue
      else:
        for _ in range(y):
          heappop(S)
          
    ans += sum(S)
    
    S = []
    heapify(S)
    x = N+1
    i = 0
    length = len(right)
    while x>=0:
      while i<length:
        klr = right[i]
        if klr[0]==x:
          heappush(S,klr[2]-klr[1])
          i += 1
 
        else:
          break
      
      y = len(S) + x - N - 1
      if y<=0:
        x -= 1
        continue
      else:
        for _ in range(y):
          heappop(S)    
    ans += sum(S)
    print(ans)
    
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

def main2(l, n):
    ans = 0
    lis = []
    heapq.heapify(lis)

    for i in range(1, n):
        for j in l[i]:
            heapq.heappush(lis, j)
        while len(lis) > i:
            ans += heapq.heappop(lis)

    return ans

def main():
    from sys import stdin

    t = int(stdin.readline().strip())

    answer = []
    for _ in range(t):

        n = int(stdin.readline().strip())
        ans = 0
        l = [[] for _ in range(n+1)]
        r = [[] for _ in range(n+1)]

        for _ in range(n):
            i, j, k = map(int, stdin.readline().strip().split())
            if j > k:
                ans += j
                l[i].append(j-k)
            elif j < k:
                if i == n:
                    ans += j
                else:
                    ans += k
                    r[n-i].append(k-j)
            else:
                ans += j

        ans -= main2(l, n) + main2(r, n)
        answer.append(ans)

    for i in answer:
        print(i)

main()

Submission status: Accepted

Solution code:
from heapq import*
def solve(x):
    s,*h=0,
    for i in range(len(x),0,-1):
        while x and x[-1][0]>=i:
            k,l,r=x.pop()
            heappush(h,(r-l,l,r))
        if h:s+=heappop(h)[1]
    return s+sum(r for _,_,r in x+h)
for _ in range(int(input())):
    n=int(input())
    x,y=[],[]
    for _ in range(n):
        k,l,r=map(int,input().split())
        if l>r:x+=(k,l,r),
        else:y+=(n-k,r,l),
    print(solve(sorted(x))+solve(sorted(y)))

Submission status: Accepted

Solution code:
import sys
from heapq import*
input=sys.stdin.buffer.readline
def solve():
    n=int(input())
    x,y=[],[]
    for _ in range(n):
        k,l,r=map(int,input().split())
        if l>r:
            x+=(k,l,r),
        else:
            y+=(n-k,r,l),
    x.sort()
    y.sort()
    s=0
    h=[]
    for i in range(len(x),0,-1):
        while x and x[-1][0]>=i:
            k,l,r=x.pop()
            heappush(h,(r-l,l,r))
        if h:s+=heappop(h)[1]
    s+=sum(r for _,_,r in x+h)
    h=[]
    for i in range(len(y),0,-1):
        while y and y[-1][0]>=i:
            k,l,r=y.pop()
            heappush(h,(r-l,l,r))
        if h:s+=heappop(h)[1]
    s+=sum(r for _,_,r in y+h)
    return s
t=int(input())
print('\n'.join(str(solve())for _ in range(t)))

Submission status: Accepted

Solution code:
import heapq

def main2(l, n):
    ans = 0
    lis = []
    heapq.heapify(lis)
    for i in range(1, n):
        for j in l[i]:
            heapq.heappush(lis, j)
        while len(lis) > i:
            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+1)]
        r = [[] for _ in range(n+1)]
        for _ in range(n):
            i, j, k = map(int, input().split())
            if j > k:
                ans += j
                l[i].append(j-k)
            elif j < k:
                if i == n:
                    ans += j
                else:
                    ans += k
                    r[n-i].append(k-j)
            else:
                ans += j

        ans -= main2(l, n) + main2(r, n)
        answer.append(ans)

    for i in answer:
        print(i)

main()