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: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint
from copy import deepcopy


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def get(self, i):
        if i == 0:
            return self.sum(0)
        return self.sum(i) - self.sum(i - 1)

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1) if i else self.sum(j - 1)

    def search_r(self, l, r):
        #右側にだんだん伸ばしていく
        # l <= x < r
        ng = l - 1
        ok = r - 1
        while ng + 1 < ok:
            mid = (ng + ok) // 2
            if self.interval_sum(l, mid + 1):
                ok = mid
            else:
                ng = mid
        return ok

    def search_l(self, l, r):
        #左側にだんだん伸ばしていく
        # l <= x < r
        ng = r
        ok = l
        while ok + 1 < ng:
            mid = (ok + ng) // 2
            if self.interval_sum(mid, ng):
                ok = mid
            else:
                ng = mid
        return ok

t = I()
for _ in range(t):
    n = I()
    ans = 0
    L = []
    K = []
    for _ in range(n):
        k, l, r = LI()
        diff = l - r
        if diff > 0:
            L += [(diff, k, 1)]
        elif diff < 0:
            L += [(-diff, k, 0)]
        ans += min(l, r)

    L.sort(reverse=True)
    bit2 = BIT(n)
    bit3 = BIT(n)
    for j in range(n):
        bit2.add(j, 1)
        bit3.add(j, 1)
    for d, ki, flg in L:
        if flg:
            if bit2.sum(ki - 1) == 0:
                continue
            else:
                idx = bit2.search_l(0, ki)
                if bit3.get(idx) and bit3.search_r(idx + 1, n):
                    bit3.add(idx, 1)
                    nxt_idx = bit3.search_r(idx + 1, n)
                    bit3.add(nxt_idx, -1)
                bit2.add(idx, -1)
                ans += d
        else:
            if bit3.interval_sum(ki, n) == 0:
                continue
            else:
                idx2 = bit3.search_r(ki, n)
                if bit2.get(idx2) and bit2.search_l(0, idx2):
                    bit2.add(idx2, 1)
                    nxt_idx2 = bit2.search_l(0, idx2)
                    bit2.add(nxt_idx2, -1)
                bit3.add(idx2, -1)
                ans += d
    print(ans)

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
    N = int(input())
    favdic_l = {}
    favdic_r = {}
    total = 0
    for i in range(N):
        K, L, R = map(int, input().split())
        if L > R:
            favdic_l.setdefault(K, [])
            favdic_l[K].append(L-R)
            total += R
        else:
            favdic_r.setdefault(N-K, [])
            favdic_r[N-K].append(R-L)
            total += L

    for dic in [favdic_l, favdic_r]:
        c_count = 0
        dic = sorted(dic.items())
        for k, v in dic:
            space = k - c_count
            c_count += len(v)
            if space > 0:
                total += sum(v[-space:])
    print(total)

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
    N = int(input())
    favdic_l = {}
    favdic_r = {}
    total = 0
    for i in range(N):
        K, L, R = map(int, input().split())
        if L > R:
            favdic_l.setdefault(K, [])
            favdic_l[K].append(L-R)
            total += R
        else:
            favdic_r.setdefault(N-K, [])
            favdic_r[N-K].append(R-L)
            total += L

    for dic in [favdic_l, favdic_r]:
        c_count = 0
        dic = sorted(dic.items())
        for k, v in dic:
            space = k - c_count
            c_count += len(v)
            if space > 0:
                total += sum(v[-space:])
print(total)

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


t = int(input())
for _ in range(t):
    n = int(input())
    camels = [tuple(map(int, input().split())) for _ in range(n)]
    camels.sort(key=lambda x: (abs(x[1] - x[2]) if x[0] < n else 0, x[0]),
                reverse=True)

    # print()
    # print('-' * 10)
    # print(*camels, sep='\n')

    bit = BIT1(n)
    ans = 0
    for i in range(1, n + 1):
        bit.add(i, 1)

    # print(bit.data)
    for k, l, r in camels:
        if k == n or l == r:
            ans += l
        else:
            s = bit.sum(k)
            if l > r:
                if s == 0:
                    # lを使えない
                    idx = bit.bisect_left(s + 1)
                    bit.add(idx, -1)
                    ans += r
                    # print(idx > k)
                else:
                    idx = bit.bisect_left(s)
                    bit.add(idx, -1)
                    ans += l
                    # print(idx <= k)
            elif r > l:
                s2 = bit.sum(n)
                if s2 - s == 0:
                    # rを使えない
                    idx = bit.bisect_left(s)
                    bit.add(idx, -1)
                    ans += l
                    # print(idx <= k)
                else:
                    idx = bit.bisect_left(s + 1)
                    bit.add(idx, -1)
                    ans += r
                    # print(idx > k)
            # print(f'{k}\t {idx}\t {abs(l - r) if k < n else 0}\t {l}\t {r}',
            #       bit.data)

    print(ans)

Submission status: Wrong Answer

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

class SegTree:
  def segfunc(self, x, y):
    return min(x, y) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    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 + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, 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

for _ in range(int(input())):
  N = int(input())
  a = []
  mxsm = 0
  for _ in range(N):
    K, L, R = map(int, input().split())
    mxsm += max(L, R)
    a.append((K, L, R))
  a.sort(key = lambda x: -abs(x[1] - x[2]))
  imos = [0] * (N + 1)
  for K, L, R in a:
    if L < R:
      imos[K] += 1
      imos[-1] -= 1
    elif L > R:
      imos[0] += 1
      imos[K] -= 1
  for i in range(N): imos[i + 1] += imos[i]
  base = 10 ** 6
  inf = 10 ** 12
  imosi = [imos[i] * base + i for i in range(N + 1)]
  seg = SegTree(N + 1, inf, imosi)
  res = 0
  for K, L, R in a:
    q = 0
    if L < R:
      q = seg.query(K, N)
    elif L > R:
      q = seg.query(0, K)
    if q == inf: res += abs(L - R)
    else: seg.update(q % base, inf)
    #print(q, K, L, R, q % base)
  print(mxsm - res)

Submission status: Wrong Answer

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

class SegTree:
  def segfunc(self, x, y):
    return min(x, y) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    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
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, 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

for _ in range(int(input())):
  N = int(input())
  a = []
  mxsm = 0
  for _ in range(N):
    K, L, R = map(int, input().split())
    mxsm += max(L, R)
    a.append((K, L, R))
  a.sort(key = lambda x: -abs(x[1] - x[2]))
  imos = [0] * (N + 1)
  for K, L, R in a:
    if L < R:
      imos[K] += 1
      imos[-1] -= 1
    elif L > R:
      imos[0] += 1
      imos[K] -= 1
  for i in range(N): imos[i + 1] += imos[i]
  base = 10 ** 6
  inf = 10 ** 12
  imosi = [imos[i] * base + i for i in range(N + 1)]
  seg = SegTree(N + 1, inf, imosi)
  res = 0
  for K, L, R in a:
    q = 0
    if L < R:
      q = seg.query(K, N)
    elif L > R:
      q = seg.query(0, K)
    if q == inf: res += abs(L - R)
    else: seg.update(q % base, inf)
    #print(q, K, L, R, q % base)
  print(mxsm - res)

Submission status: Wrong Answer

Solution code:
T = int(input())

for cases in range(T):

  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: Wrong Answer

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: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint
from copy import deepcopy


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def get(self, i):
        if i == 0:
            return self.sum(0)
        return self.sum(i) - self.sum(i - 1)

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1) if i else self.sum(j - 1)

    def search_r(self, l, r):
        #右側にだんだん伸ばしていく
        # l <= x < r
        ng = l - 1
        ok = r - 1
        while ng + 1 < ok:
            mid = (ng + ok) // 2
            if self.interval_sum(l, mid + 1):
                ok = mid
            else:
                ng = mid
        return ok

    def search_l(self, l, r):
        #左側にだんだん伸ばしていく
        # l <= x < r
        ng = r
        ok = l
        while ok + 1 < ng:
            mid = (ok + ng) // 2
            if self.interval_sum(mid, ng):
                ok = mid
            else:
                ng = mid
        return ok

t = I()
for _ in range(t):
    n = I()
    ans = 0
    L = []
    K = []
    for _ in range(n):
        k, l, r = LI()
        diff = l - r
        if diff > 0:
            L += [(diff, k, 1)]
        elif diff < 0:
            L += [(-diff, k, 0)]
        ans += min(l, r)

    L.sort(reverse=True)
    bit2 = BIT(n)
    bit3 = BIT(n)
    for j in range(n):
        bit2.add(j, 1)
        bit3.add(j, 1)
    for d, ki, flg in L:
        if flg:
            if bit2.sum(ki - 1) == 0:
                continue
            else:
                idx = bit2.search_l(0, ki)
                if bit3.get(idx) and bit3.search_r(idx, n):
                    bit3.add(idx, 1)
                    nxt_idx = bit3.search_r(idx + 1, n)
                    bit3.add(nxt_idx, -1)
                bit2.add(idx, -1)
                ans += d
        else:
            if bit3.interval_sum(ki, n) == 0:
                continue
            else:
                idx2 = bit3.search_r(ki, n)
                if bit2.get(idx2) and bit2.search_l(0, idx2):
                    bit2.add(idx2, 1)
                    nxt_idx2 = bit2.search_l(0, idx2 - 1)
                    bit2.add(nxt_idx2, -1)
                bit3.add(idx2, -1)
                ans += d
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(grid):  # fix inputs here

    console("----- solving ------")
    baseline = sum(b for a,b,c in grid)

    # pos = [a for a,b,c in grid]
    # diff = [c-b for a,b,c in grid] 
    
    char = [(a-1,c-b) for a,b,c in grid]
    char = sorted(char, key=lambda x: abs(x[1]))[::-1]

    console(baseline)
    console(char)
    console('=')

    assignment = [None for _ in char]
    right_pointer = [None for _ in char]
    left_pointer = [None for _ in char]
    discard = 0 
    for pos,diff in char:
        if assignment[pos] == None:
            assignment[pos] = max(0,diff)

        visited = [pos]
        if diff > 0:
            while pos > 0:
                if assignment[pos] == None:
                    if left_pointer[pos] == None:
                        pos -= 1
                    else:
                        visited.append(pos)
                        pos = left_pointer[pos]
                else:
                    for idx in visited:
                        left_pointer[idx] = pos-1
                    assignment[pos] = max(0,diff)
                    break
            if pos < 0:
                discard += min(0,diff)

        if diff < 0:
            pos = pos+1
            while pos < len(char):
                if assignment[pos] == None:
                    if right_pointer[pos] == None:
                        pos -= 1
                    else:
                        visited.append(pos)
                        pos = right_pointer[pos]
                else:
                    for idx in visited:
                        right_pointer[idx] = pos
                    assignment[pos] = max(0,diff)
                    break
            if pos < 0:
                discard += min(0,diff)

        if diff == 0:
            break
        
    console("res")
    console(assignment)
    console(left_pointer)
    console(right_pointer) 
    console(discard)   
    assignment = [x for x in assignment if x != None]
    
    return baseline + sum(assignment) - discard


    

    # return a string (i.e. not a list or matrix)
    return baseline


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return


for case_num in range(int(input())):
    # read line as a string
    # strr = input()

    # read line as an integer
    nrows = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    # lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for _ in range(nrows):
        grid.append(list(map(int,input().split())))

    res = solve(grid)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    # front = defaultdict(list)  # int/bool/list....
    front = defaultdict(list)
    back = defaultdict(list)
    cnt = [0] * (N + 1)
    f_cnt = [0] * (N + 1)
    b_cnt = [0] * (N + 1)
    ans = 0
    for i in range(N):
        K, L, R = [int(x) for x in input().split()]
        if L >= R or K == N:
            front[K].append(tuple((L, R)))
            f_cnt[K] += 1
        else:
            back[K + 1].append(tuple((L, R)))
            b_cnt[K + 1] += 1
        # cnt[K] += 1

    b_cum = 0
    for i in range(N, 0, -1):   # 後ろから
        if b_cnt[i] == 0: continue
        if b_cum + b_cnt[i] <= N + 1 - i: # 希望を満たせる
            for l, r in back[i]:
                ans += r
            b_cum += b_cnt[i]
        else:
            drop = b_cum + b_cnt[i] - (N + 1 - i)  # 希望を満たせないラクダの数
            back[i].sort(key = lambda x : x[1] - x[0])  # 落としても良い順
            for j in range(drop):
                ans += back[i][j][0]
            for j in range(drop, b_cnt[i]):
                ans += back[i][j][1]
            b_cum = N + 1 - i # 希望を満たしたラクダの数

    f_cum = 0
    for i in range(1, N + 1):   # 前から
        if f_cnt[i] == 0: continue
        if f_cum + f_cnt[i] <= i: # 希望を満たせる
            for l, r in front[i]:
                ans += l
            f_cum += f_cnt[i]
        else:
            drop = f_cum + f_cnt[i] - i  # 希望を満たせないラクダの数
            front[i].sort(key = lambda x : x[0] - x[1])  # 落としても良い順
            for j in range(drop):
                ans += front[i][j][1]
            for j in range(drop, f_cnt[i]):
                ans += front[i][j][0]
            f_cum = i # 希望を満たしたラクダの数

    print(ans)

Submission status: Wrong Answer

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

t = int(input())

for loop in range(t):
    n = int(input())
    lg = []
    rg = []
    others = 0
    for i in range(n):
        k,l,r = map(int,input().split())
        if l > r:
            lg.append([k,l,r])
        elif l == r:
            others += l
        else:
            rg.append([n-k,l,r])
    lg.sort(key=lambda x:(x[0],-x[1]))
    rg.sort(key=lambda x:(x[0],-x[2]))
    fill = 0
    ans = 0
    for l in lg:
        if l[0] > fill:
            fill += 1
            ans += l[1]
        else:
            ans += l[2]
    fill = 0
    for r in rg:
        if r[0] > fill:
            fill += 1
            ans += r[2]
        else:
            ans += r[1]
    # print(lg)
    # print(rg)
    print(ans+others)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
  n=int(input())
  s=0
  list1=[]
  list2=[]
  for i in range(n):
    k,l,r=map(int,input().split())
    s+=min(l,r)
    if l-r>0: list1.append((l-r,k))
    else: list2.append((r-l,n-k))

  list1=sorted(list1, reverse=True, key=lambda x: x[0])
  list2=sorted(list2, reverse=True, key=lambda x: x[0])

  dic={p:0 for p in range(1,n+1)}
  for x in list1:
    w=x[1]
    dic[w]+=1
    if dic[w]<=w: s+=x[0]

  dic={p:0 for p in range(n)}
  for x in list2:
    w=x[1]
    dic[w]+=1
    if dic[w]<=w: s+=x[0]
  print(s)

Submission status: Wrong Answer

Solution code:
T = int(input())

import heapq  # heapqライブラリのimport

for case in range(T):
    N = int(input())
    KLR = []
    for i in range(N):
        KLR.append(list(map(int,input().split())))
    heapq.heapify(KLR)
    Ls = [[0,0,0]]
    heapq.heapify(Ls)
    Rs = []
    now = 0
    A,AL,AR = heapq.heappop(KLR)
    while now<=N-1:
        if now<A-1:
            heapq.heappush(Ls, [0,0,0])
            now+=1
        elif now==A-1:
            test = heapq.heappop(Ls)
            if AL-AR>=test[1]-test[2]:
                heapq.heappush(Ls,[A,AL,AR])
            else:
                heapq.heappush(Ls,test)
                if A==N:
                    Rs.append(AL)
                else:
                    Rs.append(AR)
            if len(KLR)==0:
                break
            A,AL,AR = heapq.heappop(KLR)
    out = 0
    for i in range(len(Ls)):
        out += Ls[i][1]
    for i in range(len(Rs)):
        out += Rs[i]
    print(out)

Submission status: Wrong Answer

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)
  data.sort(key=lambda x:-abs(x[1]-x[2]))
  ans = 0
  MAE = [i for i in range(N)]
  def CANSIT_MAE(x):
    if MAE[x] == -1:
      return -1
    elif MAE[x] == x:
      MAE[x] = x-1
      USHIRO[N-1-x] = N-1-x-1
      return x
    else:
      MAE[x] = CANSIT_MAE(MAE[x])
      if MAE[x] != -1:
        USHIRO[N-1-MAE[x]] = N-1-MAE[x]-1
      return MAE[x]
  USHIRO = [i for i in range(N)]
  def CANSIT_USHIRO(x):
    if USHIRO[x] == -1:
      return -1
    elif USHIRO[x] == x:
      USHIRO[x] = x-1
      MAE[N-1-x] = N-1-x-1
      return x
    else:
      USHIRO[x] = CANSIT_USHIRO(USHIRO[x])
      if USHIRO[x] != -1:
        MAE[N-1-USHIRO[x]] = N-1-USHIRO[x]-1
      return USHIRO[x]
  for K,L,R in data:
    if L==R or K==N:
      ans += L
    elif L>R:
      if CANSIT_MAE(K-1)!=-1:
        ans += L
      else:
        ans += R
    else:
      if CANSIT_USHIRO(N-K)!=-1:
        ans += R
      else:
        ans += L
  print(ans)

Submission status: Wrong Answer

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:
                queue[0] = 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:
                queue[0] = v
    ans += sum(queue)
    print(ans)