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
import heapq
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


T = ni()

for _ in range(T):
    N = ni()
    ans = 0
    plus = []
    minus = []
    for _ in range(N):
        k, l, r = na()
        if l > r:
            plus.append([k, l-r])
            ans += r
        elif l < r:
            if N != k:
                minus.append([N-k, r-l])
            ans += l
        else:
            ans += l
    plus = sorted(plus, key=lambda x: x[0] * 10 ** 10 - x[1])
    minus = sorted(minus, key=lambda x: x[0] * 10 ** 10 - x[1])
    queue = []
    for p in plus:
        i, v = p 
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                heapq.heappushpop(queue, v)
    ans += sum(queue)
    queue = []
    for m in minus:
        i, v = m
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                heapq.heappushpop(queue, v)
    ans += sum(queue)
    print(ans)

Submission status: Accepted

Solution code:
import heapq

t = int(input())
for _ in range(t):
    n = int(input())
    l = [[] for i in range(n+1)]
    r = [[] for i in range(n+1)]
    ans = 0
    for i in range(n):
        a,b,c = map(int,input().split())
        if b > c:
            l[a].append(b-c)
            ans += c
        else:
            r[a].append(c-b)
            ans += b
    q = []
    for i, lx in enumerate(l):
        for x in lx:
            if len(q) < i:
                heapq.heappush(q,x)
            else:
                heapq.heappushpop(q,x)
    ans += sum(q)
    q = []
    for i,rx in enumerate(r[::-1][1:],1):
        for x in rx:
            if len(q) < i:
                heapq.heappush(q,x)
            else:
                heapq.heappushpop(q,x)
    ans += sum(q)
    print(ans)

Submission status: Accepted

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

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

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

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]

class SegtreeMax():
    def __init__(self, aa):
        n=len(aa)
        self.inf = 10 ** 16
        tree_width = 2
        while tree_width < n:
            tree_width *= 2
        self.tree_width = tree_width
        self.tree = [0] * (tree_width * 2 - 1)
        self.tree[self.tree_width-1:self.tree_width-1+len(aa)]=aa
        for i in range(tree_width-2,-1,-1):
            self.tree[i]=max(self.tree[i*2+1],self.tree[i*2+2])

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = max(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最小値
    def max(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.max(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.max(l, r, seg_i * 2 + 2, segM, segR)
        return max(ret0, ret1)

for _ in range(II()):
    n=II()
    hp=[]
    hpr=[]
    ans=0
    for _ in range(n):
        k,l,r=MI()
        if r<l:heappush(hp,(r-l,l,r,k))
        elif r>l:heappush(hpr,(-r+l,l,r,k))
        else:ans+=r

    st=SegtreeMax(list(range(n+5)))
    for i in range(n+1):st.update(i,i)
    while hp:
        d,l,r,k=heappop(hp)
        i=st.max(0,k+1)
        if i:
            ans+=l
            st.update(i,0)
        else:
            ans+=r

    st=SegtreeMax(list(range(n+5)))
    for i in range(n+1):st.update(i,i)
    while hpr:
        d,l,r,k=heappop(hpr)
        k=n-k
        i=st.max(0,k+1)
        if i:
            ans+=r
            st.update(i,0)
        else:
            ans+=l

    print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop

T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    first = []
    last = []
    base = 0
    base_max = 0
    for _ in range(N):
        k, l, r = map(int, input().split())
        if k == N:
            r = l
        if l > r:
            first.append([k, l - r])
        elif r > l:
            last.append([N - k, r - l])
        base += min(l, r)
        base_max += max(l, r)
    first.sort()
    last.sort()

    pool = []
    for k, p in first:
        if len(pool) < k:
            heappush(pool, p)
        else:
            if pool and pool[0] < p:
                heappushpop(pool, p)
    base += sum(pool)
    pool = []
    for k, p in last:
        if len(pool) < k:
            heappush(pool, p)
        else:
            if pool and pool[0] < p:
                heappushpop(pool, p)
    base += sum(pool)
    ans.append(base)
    pass
print(*ans, sep="\n")

Submission status: Accepted

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

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq

class BinaryIndexedTree:
    # Initialize BIT with non-zero value
    def __init__(self, array):
        self.len = len(array)
        self.data = [0] + array
        self.build()

    def build(self):
        for i in range(1, self.len):
            if i + (i & -i) > self.len:
                continue
            self.data[i + (i & -i)] += self.data[i]

    # Add w to a[x] (0-indexed)
    def add(self, x, w):
        x += 1
        while x <= self.len:
            self.data[x] += w
            x += x & -x

    # Get Sum of a[0 : x) (0-indexed)
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.data[x]
            x -= x & -x
        return ret

    # Get first index s.t. sum a[0 : index) >= w
    def bisect_left(self, w):
        if w <= 0:
            return 0
        x = 0
        delta = pow(2, (self.len - 1).bit_length())
        while delta > 0:
            if x + delta <= self.len and self.data[x + delta] < w:
                w -= self.data[x + delta]
                x += delta
            delta >>= 1
        return x

t = int(input())
for _ in range(t):
    n = int(input())
    q = []
    base = 0
    left = BinaryIndexedTree([0] * n)
    right = BinaryIndexedTree([0] * n)
    left_bag = [[] for _ in range(n)]
    right_bag = [[] for _ in range(n)]
    for _ in range(n):
        k, l, r = map(int, input().split())
        if k == n:
            base += l
            continue
        if l == r:
            base += l
        elif l > r:
            q.append((l-r, 0, k-1))
            base += r
            left_bag[k-1].append(l-r)
        else:
            q.append((r-l, 1, n-k-1))
            base += l
            right_bag[n-k-1].append(r-l)
    
    left_bag.reverse()
    hq = []
    for bag in left_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, -item)
        if hq:
            base += -heapq.heappop(hq) 
    right_bag.reverse()
    hq = []
    for bag in right_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, -item)
        if hq:
            base += -heapq.heappop(hq) 
    print(base)

Submission status: Accepted

Solution code:
import heapq as hq

T = int(input())
for _ in range(T):
    N = int(input())
    Cp = []
    Cn = []
    ans = 0
    for _ in range(N):
        K, L, R = map(int, input().split())
        D = L-R
        if D>=0:
            ans += R
            Cp.append((K,D))
        else:
            ans += L
            Cn.append((N-K,-D))

    Cp = sorted(Cp, reverse=True)
    Cn = sorted(Cn, reverse=True)
    Np = len(Cp)
    Nn = len(Cn)

    i = 0
    h = []
    for n in range(Np, 0, -1):
        while i<Np:
            k, d = Cp[i]
            if k<n: break
            hq.heappush(h, -d)
            i+=1

        if len(h): ans += -hq.heappop(h)

    i = 0
    h = []
    for n in range(Nn, 0, -1):
        while i<Nn:
            k, d = Cn[i]
            if k<n: break
            hq.heappush(h, -d)
            i+=1

        if len(h): ans += -hq.heappop(h)

    print(ans)

Submission status: Accepted

Solution code:
import heapq

def func():
    N = int(input())
    L_list = []
    L_ind = [[]for i in range(N)]
    R_list = []
    R_ind = [[]for i in range(N+1)]
    ans = 0
    for i in range(N):
        k,l,r = map(int,input().split())
        if l > r:
            L_list.append(l-r)
            L_ind[k-1].append(len(L_list)-1)
            ans += r
        elif r > l:
            R_list.append(r-l)
            R_ind[N-k].append(len(R_list)-1)
            ans += l
        else:
            ans += l

    L_heap = []
    for i in range(N):
        for j in L_ind[i]:
            heapq.heappush(L_heap,L_list[j])
        while len(L_heap) > i+1:
            heapq.heappop(L_heap)
    R_heap = []
    for i in range(N):
        for j in R_ind[i+1]:
            heapq.heappush(R_heap,R_list[j])
        while len(R_heap) > i+1:
            heapq.heappop(R_heap)
    return(ans+sum(L_heap)+sum(R_heap))
    

T= int(input())
for i in range(T):
    print(func())

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
t=int(input())
import heapq
for _ in range(t):
  n=int(input())
  ans=0
  C=[]
  D=[]
  for i in range(n):
    k,l,r=map(int,input().split())
    if l>r:
      C.append((k,l-r))
      ans+=r
    else:
      D.append((n-k,r-l))
      ans+=l
  C.sort(key=lambda x:(x[0],x[1]), reverse=True)
  D.sort(key=lambda x:(x[0],x[1]), reverse=True)
  c,d=len(C),len(D)
  H=[]
  cur=0
  for i in range(1,c+1)[::-1]:
    while cur<c:
      k,l=C[cur]
      if k<i:
        break
      else:
        heapq.heappush(H,(-l,k))
        cur+=1
    if H:
      ll,kk=heapq.heappop(H)
      ll=-ll
      ans+=ll
  H=[]
  cur=0
  for i in range(1,d+1)[::-1]:
    while cur<d:
      k,l=D[cur]
      if k<i:
        break
      else:
        heapq.heappush(H,(-l,k))
        cur+=1
    if H:
      ll,kk=heapq.heappop(H)
      ll=-ll
      ans+=ll
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
T = int(input())

for _ in range(T):
    N = int(input())
    score = 0
    want_left = []
    want_right = []
    for _ in range(N):
        K, L, R = map(int, input().split())
        if K == N:
            score += L
        elif L == R:
            score += L
        elif L > R:
            want_left.append((K, L-R))
            score += R
        else:
            want_right.append((N-K, R-L))
            score += L

    want_left.sort()
    left_q = []
    index = 0
    i = 0
    while index < len(want_left):
        i += 1
        while index < len(want_left) and want_left[index][0] <= i:
            heapq.heappush(left_q, want_left[index][1])
            index += 1
        while len(left_q) > i:
            heapq.heappop(left_q)
    score += sum(left_q)
    
    want_right.sort()
    right_q = []
    index = 0
    i = 0
    while index < len(want_right):
        i += 1
        while index < len(want_right) and want_right[index][0] <= i:
            heapq.heappush(right_q, want_right[index][1])
            index += 1
        while len(right_q) > i:
            heapq.heappop(right_q)
    score += sum(right_q)

    print(score)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
INF=10**6
class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        self.tot=0
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        self.tot=0
        for i,x in enumerate(seq,1):
            self.tot+=x
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, val):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += val
            i += i & -i
        self.tot+=val
    
    def find(self,k):#k番目（最小は１）の要素,使うときは数列のサイズとbitのサイズを合わせること
        if k>self.tot: return self.size
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = list(tuple(map(int, input().split())) for i in range(N)) #改行行列

    def dif(s):
        L=s[1]
        R=s[2]
        return abs(L-R)
    S.sort(key=dif,reverse=1)

    l1=BIT(N)
    l2=BIT(N)
    a=[1]*N
    l1.initialize(a)
    l2.initialize(a)
    ans=0
    for K,L,R in S:
        if L>R:
            t=l1
            la=L
            mi=R
        elif R>L:
            t=l2
            la=R
            mi=L
            K=N-K
        else:
            ans+=R
            continue
        if K==0:
            ans+=mi
            continue
            
        x=t.sum(K)
        if x!=0:
            ins=t.find(x)
            t.add(ins,-1)
            ans+=la
        else:
            ans+=mi
    print(ans)




        



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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

t = int(readline())
q = list(map(int,read().split()))

now = 0
ans = [0] * t
for cyc in range(t):
    n = q[now]
    klr = q[now+1: now+1+3*n]
    now = now+1+3*n

    it = iter(klr)
    lc = []
    rc = []
    min_p = 0
    for x,y,z in zip(it,it,it):
        if(y==z):
            min_p += y
        elif(y>z):
            min_p += z
            lc.append((x,y-z))
        else:
            min_p += y
            rc.append((n-x,z-y))

    res = min_p
    lc.sort()
    rc.sort()

    for cam in [lc,rc]:
        hq = []
        for i in range(n,0,-1):
            if(len(cam)>0):
                while(cam[-1][0] == i):
                    x,p = cam.pop()
                    heappush(hq,p*-1)
                    if(len(cam)==0):
                        break
            if(hq):
                res += heappop(hq)*-1

    ans[cyc] = res

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
from heapq import *
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

t = int(input())

ans = [0]*t
for i in range(t):
    n = int(input())
    plus = [[] for i in range(n)]
    minus = [[] for i in range(n)]
    delta = 0
    for _ in range(n):
        k,l,r = map(int,input().split())
        k -= 1
        ans[i] += r
        if l-r > 0:
            plus[k].append(l-r)
        elif l-r < 0:
            minus[k].append(l-r)
            delta += l-r
    can = 0
    pq = []
    for j in range(n-1,-1,-1):
        while plus[j]:
            heappush(pq,-plus[j].pop())
        if pq:
            delta += -heappop(pq)
            can += 1
    pqm = []
    for j in range(n):
        if j >= can and pqm:
            delta += -heappop(pqm)
        while minus[j]:
            heappush(pqm,minus[j].pop())
    ans[i] += delta
print("\n".join(str(i) for i in ans))

Submission status: Accepted

Solution code:
class SegTree():
    def segfunc(self, x, y):
        return x + y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def solve():
    n = int(input())
    camel = [list(map(int, input().split())) for _ in range(n)]
    camel_L = []
    camel_R = []
    for i in range(n):
        if camel[i][1] > camel[i][2]:
            camel_L.append([camel[i][0], camel[i][1], camel[i][2]])
        else:
            camel_R.append([camel[i][0], camel[i][1], camel[i][2]])
    ans = 0
    camel_L.sort(key=lambda x: (x[2]- x[1]))
    camel_R.sort(key=lambda x: (x[1]- x[2]))
    seg = SegTree(0, n, [0]*n)
    nex = [i for i in range(n)]
    for i in range(len(camel_L)):
        k, l, r = camel_L[i]
        q = seg.query(0, k)
        if q < k:
            p = nex[k-1]
            while p != nex[p]:
                pre = p
                p = nex[p]
                nex[pre] = nex[p]-1
            nex[p] = p-1
            seg.update(p, 1)
            ans += l
        else:
            ans += r
    seg = SegTree(0, n, [0]*n)
    nex = [i for i in range(n)]
    for i in range(len(camel_R)):
        k, l, r = camel_R[i]
        q = seg.query(k, n)
        if q < n-k:
            p = nex[k]
            while p != nex[p]:
                pre = p
                p = nex[p]
                nex[pre] = nex[p]+1
            nex[p] = p+1
            seg.update(p, 1)
            ans += r
        else:
            ans += l
    return ans

def main():
    t = int(input())
    ans = [None]*t
    for i in range(t):
        ans[i] = solve()
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

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


t = int(input())
for _ in range(t):
    n = int(input())
    info = [list(map(int, input().split())) for i in range(n)]
    p_li = []
    m_li = []
    ans = 0
    for k, l, r in info:
        diff = l - r
        if diff > 0:
            p_li.append((k - 1, abs(diff)))
            ans += r
        elif diff < 0:
            m_li.append((n - k - 1, abs(diff)))
            ans += l
        else:
            ans += l

    p_li = sorted(p_li, reverse=True)
    l = 0
    q = []
    for i in range(n)[::-1]:
        while l < len(p_li) and p_li[l][0] == i:
            heapq.heappush(q, -p_li[l][1])
            l += 1
        if q:
            val = -heapq.heappop(q)
            ans += val

    m_li = sorted(m_li, reverse=True)
    l = 0
    q = []
    for i in range(n)[::-1]:
        while l < len(m_li) and m_li[l][0] == i:
            heapq.heappush(q, -m_li[l][1])
            l += 1
        if q:
            val = -heapq.heappop(q)
            ans += val
    print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappushpop

t = int(sys.stdin.buffer.readline())
buf = []
for _ in range(t):
    n = int(sys.stdin.buffer.readline())
    lll = []
    rrr = []
    ans = 0
    for i in range(n):
        k, l, r = map(int, sys.stdin.buffer.readline().split())
        if l >= r:
            lll.append((k, l - r))
            ans += l
        else:
            rrr.append((n - k, r - l))
            ans += r
    lll.sort()
    rrr.sort()
    q = []
    for k, rl in lll:
        if len(q) < k:
            heappush(q, rl)
        else:
            nrl = heappushpop(q, rl)
            ans -= nrl
    q = []
    for k, lr in rrr:
        if len(q) < k:
            heappush(q, lr)
        else:
            nlr = heappushpop(q, lr)
            ans -= nlr

    buf.append(ans)

print('\n'.join(map(str, buf)))