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:
#pragma region Macro_and_Function
#pragma region Basic
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i < i##_len; i++)
#define FORD(i, a, b) for (int i = (a), i##_len = (b); i > i##_len; i--)
#define FORR(t, a) for (auto t : a)
#define ALL(x) (x).begin(), (x).end()  // sortなどの引数を省略したい
#define INSERTER(x) inserter((x), (x).end())  // inserter
#define GET(i, j) get<j>(i)
#define MT(x, ...) make_tuple(x, __VA_ARGS__)
#define SZ(x) ((int)(x).size())
#define PB push_back
#ifdef _DEBUG
#define PRE_COMMAND             \
    std::cin.rdbuf(in.rdbuf()); \
    cout << fixed << setprecision(15);
#else
#define PRE_COMMAND cout << fixed << setprecision(15);
#endif
const double EPS = 1e-10;
const double PI = acos(-1.0);
template <class T>
T DEG_2_RAD(T deg) {
    return deg * PI / 180;
}
template <class T>
T RAD_2_DEG(T rad) {
    return rad * 180 / PI;
}
template <class T>
auto MAX(T& seq) {
    return *max_element(seq.begin(), seq.end());
}
template <class T>
auto MIN(T& seq) {
    return *min_element(seq.begin(), seq.end());
}
template <class T>
auto SUM(T& seq) {
    T temp{0};
    auto& temp2 = temp[0];
    return accumulate(seq.begin(), seq.end(), temp2);
}
template <class T>
void SORT(T& seq) {
    sort(seq.begin(), seq.end());
}
template <class T, class S>
void SORT(T& seq, S& sort_order) {
    sort(seq.begin(), seq.end(), sort_order);
}
template <class T>
void SORTR(vector<T>& seq) {
    sort(seq.begin(), seq.end(), greater<T>());
}
template <class T>
void CHMAX(T& a, const T& b) {
    if (a < b) { a = b; }
}
template <class T>
void CHMIN(T& a, const T& b) {
    if (b < a) { a = b; }
}
template <class T>
set<T> VECTOR_2_SET(vector<T>& v) {
    set<T> s;
    for (auto ele : v) { s.insert(ele); }
    return s;
}
template <class T>
vector<T> SET_2_VECTOR(set<T>& s) {
    vector<T> v;
    for (auto ele : s) { v.push_back(ele); }
    return v;
}
template <class T, class S, class R>
long long pow(T n_0, S k_0, R mod_0) {
    long long n = n_0;
    long long k = k_0;
    long long mod = mod_0;
    long long now = 1;
    while (true) {
        if (k & 1) { now = now * n % mod; }
        k >>= 1;
        if (k == 0) { return now; }
        n = (n * n) % mod;
    }
}
#pragma endregion Basic
#pragma region overload
template <class T, class S>
void operator+=(vector<T>& l, S& r) {
    for (auto i : r) { l.push_back(i); }
}
template <class T, class S>
void operator+=(set<T>& l, S& r) {
    for (auto i : r) { l.insert(i); }
}
template <class T, class S>
void operator+=(multiset<T>& l, S& r) {
    for (auto i : r) { l.insert(i); }
}
void operator*=(string& l, const size_t& r) {
    string str = l;
    for (size_t i = 0; i < r - 1; i++) { l += str; }
}
template <class T, class S>
vector<T> operator+(vector<T>& l, S& r) {
    vector<T> l_copy = l;
    for (auto i : r) { l_copy.push_back(i); }
    return l_copy;
}
template <class T>
vector<T> operator+(const vector<T> l, const vector<T>& r) {
    vector<T> l_copy = l;
    for (auto i : r) { l_copy.push_back(i); }
    return l_copy;
}
template <class T, class S>
set<T> operator+(set<T>& l, S& r) {
    set<T> l_copy = l;
    for (auto i : r) { l_copy.insert(i); }
    return l_copy;
}
template <class T>
set<T> operator+(const set<T> l, const set<T>& r) {
    set<T> l_copy = l;
    for (auto i : r) { l_copy.insert(i); }
    return l_copy;
}
template <class T, class S>
multiset<T> operator+(multiset<T>& l, S& r) {
    set<T> l_copy = l;
    for (auto i : r) { l_copy.insert(i); }
    return l_copy;
}
template <class T>
multiset<T> operator+(const multiset<T> l, const set<T>& r) {
    set<T> l_copy = l;
    for (auto i : r) { l_copy.insert(i); }
    return l_copy;
}
string operator*(const string l, const size_t& r) {
    string str = l;
    for (size_t i = 0; i < r - 1; i++) { str += l; }
    return str;
}
#pragma endregion overload
#pragma region Input
template <class Head>
void INPUT(vector<Head>& head);
template <size_t N, class Head>
void INPUT(array<Head, N>& head);
template <class T1>
void INPUT(tuple<T1>& t);
template <class T1, class T2>
void INPUT(tuple<T1, T2>& t);
template <class T1, class T2, class T3>
void INPUT(tuple<T1, T2, T3>& t);
template <class T1, class T2, class T3, class T4>
void INPUT(tuple<T1, T2, T3, T4>& t);
template <class T1, class T2, class T3, class T4, class T5>
void INPUT(tuple<T1, T2, T3, T4, T5>& t);
template <class Head>
void INPUT(Head& head);
template <class Head, class... Tail>
void INPUT(Head& head, Tail&... tail);
//本体
template <class Head>
void INPUT(vector<Head>& head) {
    for (size_t i = 0; i < head.size(); i++) { INPUT(head[i]); }
}
template <size_t N, class Head>
void INPUT(array<Head, N>& head) {
    for (size_t i = 0; i < head.size(); i++) { INPUT(head[i]); }
}
template <class T1>
void INPUT(tuple<T1>& t) {
    cin >> get<0>(t);
}
template <class T1, class T2>
void INPUT(tuple<T1, T2>& t) {
    cin >> get<0>(t) >> get<1>(t);
}
template <class T1, class T2, class T3>
void INPUT(tuple<T1, T2, T3>& t) {
    cin >> get<0>(t) >> get<1>(t) >> get<2>(t);
}
template <class T1, class T2, class T3, class T4>
void INPUT(tuple<T1, T2, T3, T4>& t) {
    cin >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
}
template <class T1, class T2, class T3, class T4, class T5>
void INPUT(tuple<T1, T2, T3, T4, T5>& t) {
    cin >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);
}
template <class Head>
void INPUT(Head& head) {
    cin >> head;
}
template <class Head, class... Tail>
void INPUT(Head& head, Tail&... tail) {
    INPUT(head);
    INPUT((tail)...);
}
#pragma endregion Input
#pragma region Print
template <class T1>
void PRINT2(tuple<T1> t);
template <class T1, class T2>
void PRINT2(tuple<T1, T2> t);
template <class T1, class T2, class T3>
void PRINT2(tuple<T1, T2, T3> t);
template <class T1, class T2, class T3, class T4>
void PRINT2(tuple<T1, T2, T3, T4> t);
template <class T1, class T2, class T3, class T4, class T5>
void PRINT2(tuple<T1, T2, T3, T4, T5> t);
template <class Head>
void PRINT2(vector<Head> head);
template <class Head>
void PRINT2(vector<vector<Head>> head);
template <size_t N, class Head>
void PRINT2(vector<array<Head, N>> head);
template <class... Head>
void PRINT2(vector<tuple<Head...>> head);
template <size_t N, class Head>
void PRINT2(array<Head, N> head);
template <class Head>
void PRINT2(Head head);
template <class Head, class... Tail>
void PRINT2(Head head, Tail... tail);
template <class Head>
void PRINT(Head head);
template <class... Head>
void PRINT(Head... head);
template <int N, class Head>
void PRINT(Head head);
template <class T1>
void PRINT2(tuple<T1> t) {
    PRINT2(get<0>(t));
}
template <class T1, class T2>
void PRINT2(tuple<T1, T2> t) {
    PRINT2(get<0>(t), get<1>(t));
}
template <class T1, class T2, class T3>
void PRINT2(tuple<T1, T2, T3> t) {
    PRINT2(get<0>(t), get<1>(t), get<2>(t));
}
template <class T1, class T2, class T3, class T4>
void PRINT2(tuple<T1, T2, T3, T4> t) {
    PRINT2(get<0>(t), get<1>(t), get<2>(t), get<3>(t));
}
template <class T1, class T2, class T3, class T4, class T5>
void PRINT2(tuple<T1, T2, T3, T4, T5> t) {
    PRINT2(get<0>(t), get<1>(t), get<2>(t), get<3>(t), get<4>(t));
}
template <class Head>
void PRINT2(vector<Head> head) {
    for (auto i = head.begin(); i != head.end(); i++) {
        PRINT2(*i);
        if (i != head.end() - 1) { cout << " "; }
    }
}
template <class Head>
void PRINT2(vector<vector<Head>> head) {
    for (auto i = head.begin(); i != head.end(); i++) {
        PRINT2(*i);
        if (i != head.end() - 1) { cout << endl; }
    }
}
template <size_t N, class Head>
void PRINT2(vector<array<Head, N>> head) {
    for (auto i = head.begin(); i != head.end(); i++) {
        PRINT2(*i);
        if (i != head.end() - 1) { cout << endl; }
    }
}
template <class... Head>
void PRINT2(vector<tuple<Head...>> head) {
    for (auto i = head.begin(); i != head.end(); i++) {
        PRINT2(*i);
        if (i != head.end() - 1) { cout << endl; }
    }
}
template <size_t N, class Head>
void PRINT2(array<Head, N> head) {
    for (auto i = head.begin(); i != head.end(); i++) {
        PRINT2(*i);
        if (i != head.end() - 1) { cout << " "; }
    }
}
template <class Head>
void PRINT2(Head head) {
    cout << head;
}
template <class Head, class... Tail>
void PRINT2(Head head, Tail... tail) {
    PRINT2(head);
    cout << " ";
    PRINT2((tail)...);
}
template <class Head>
void PRINT(Head head) {
    PRINT2(head);
    cout << endl;
}
template <class... Head>
void PRINT(Head... head) {
    PRINT2((head)...);
    cout << endl;
}
template <int N, class Head>
void PRINT(Head head) {
    PRINT2(head);
    cout << endl;
}
#pragma endregion Print
#pragma endregion Macro_and_Function

auto order = [](const auto& x, const auto& y) {
    array<ll, 2> x2, y2;
    // +は昇順、-は降順
    x2 = {-GET(x, 0), GET(x, 1)};
    y2 = {-GET(y, 0), GET(y, 1)};
    return x2 < y2;
};

int main() {
    PRE_COMMAND
    int t;
    INPUT(t);
    REP(i, t) {
        int n;
        ll total = 0;
        INPUT(n);
        set<int> s_l, s_r;
        vector<tuple<ll, int>> v_l, v_r;
        REP(j, n) {
            s_l.insert(-j);
            s_r.insert(-j);
        }
        s_l.insert(1);
        s_r.insert(1);
        REP(j, n) {
            int k;
            ll l, r;
            INPUT(k, l, r);
            if (l > r) {
                v_l.PB(MT(l - r, k - 1));
            } else if (l < r) {
                v_r.PB(MT(r - l, n - k - 1));
            }
            total += min(l, r);
        }
        SORT(v_l, order);
        SORT(v_r, order);
        FORR(tmp, v_l) {
            ll d;
            int k;
            tie(d, k) = tmp;
            int lb = *s_l.lower_bound(-k);
            if (lb < 1) {
                total += d;
                s_l.erase(lb);
            }
        }
        FORR(tmp, v_r) {
            ll d;
            int k;
            tie(d, k) = tmp;
            int lb = *s_r.lower_bound(-k);
            if (lb < 1) {
                total += d;
                s_r.erase(lb);
            }
        }
        PRINT(total);
    }
}

Submission status: Runtime Error

Solution code:
import heapq as hp
# heapq.heappush(heap,item)
# heapq.heppop(heap) 最小値　最初のやつの取り出し
t=int(input())
for i in range(t):
    n=int(input())
# 左からkまでなら、+x lef[k]=[3,4,5]
    lef=[[] for i in range(n+1)]
    rig=[[] for i in range(n+1)]
    a=[]
    hp.heapify(a)
    ans=0
    lefcnt=0

    for i in range(n):
        k,l,r=map(int,input().split())
        if(l>=r):
            ans+=r
            lefcnt+=1
            tmp=l-r
            lef[k].append(tmp)
        else:
            ans+=l
            tmp=r-l
            rig[n-k].append(tmp)
    for i in range(lefcnt,0,-1):
        for j in lef[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp

    a=[]
    hp.heapify(a)
    for i in range(n-lencnt,0,-1):
        for j in rig[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp
    print(ans)

Submission status: Runtime Error

Solution code:
T = int(input())
for fakevar in range(T):
	N=int(input())
	p=[]
	n=[]
	min_p=0
	min_n=0
	for fakevar2 in range(N):
		K,L,R=map(int, input().split())
		if L-R>=0:
			p+=[[L-R,K-1]]
			min_p+=R
		else:
			n+=[[R-L,N-K-1]]
			min_n+=L
	
	p.sort(key=lambda x: x[0], reverse=True)
	n.sort(key=lambda x: x[0], reverse=True)
	p_set=set([])
	n_set=set([])
	p_score=0
	n_score=0
	for i in range(len(p)):
		j=min(p[i][1],len(p)-1)
		while j in p_set and j>=0:
			j+=(-1)
		
		if j>=0:
			p_set.add(j)
			p_score+=p[i][0]
	
	for i in range(len(n)):
		j=min(n[i][1],len(n)-1)
		while n_array[j]>-1 and j>=0:
			j+=(-1)
		
		if j>=0:
			n_array[j]=n[i][0]
			n_score+=n[i][0]
	
	print(p_score+n_score+min_p+min_n)

		





# 2darray [[0] * 4 for i in range(3)]

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit, i8, b1


@njit((i8, i8[:, :]), cache=True)
def solve(N, camels):
    L = np.zeros(N, dtype=b1)
    R = np.zeros(N, dtype=b1)
    full_idx_l, full_idx_r = 0, N - 1
    ans = 0
    for k, l, r in camels:
        if l > r:
            k -= 1
            if k < full_idx_l:
                ans += r
                continue
            while L[k]:
                k -= 1
                if k < full_idx_l:
                    ans += r
                    continue
            L[k] = True
            ans += l
            while full_idx_l < N and L[full_idx_l]:
                full_idx_l += 1
        else:
            if k > full_idx_r:
                ans += l
                continue
            while R[k]:
                k += 1
                if k > full_idx_r:
                    ans += l
                    continue
            R[k] = True
            ans += r
            while full_idx_r >= 0 and R[full_idx_r]:
                full_idx_r -= 1
    return ans


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]), reverse=True)
    camels = np.array(camels, dtype=np.int64)
    print(solve(N, camels))

Submission status: Runtime Error

Solution code:
from collections import namedtuple
import sys
input = sys.stdin.readline

Camel = namedtuple("Camel", "k v".split(" "))
def read_int():
    return int(input())

def read_int_array():
    return [int(ss) for ss in input().split()]

class SegmentNode:
    def __init__(self, minidx, maxidx, capacity, occupied, left, right):
        self.minidx = minidx
        self.maxidx = maxidx
        self.capacity = capacity
        self.occupied = occupied
        self.left = left
        self.right = right

    def __repr__(self):
        return f"[{self.minidx}-{self.maxidx}, {self.occupied}/{self.capacity}]"

    def print_tree(self, lvl = 0):
        print((" " * lvl) + self.__repr__())
        if self.left:
            self.left.print_tree(lvl + 2)
        if self.right:
            self.right.print_tree(lvl + 2)

    def occupy(self, rightmost_idx):
        if self.minidx > rightmost_idx:
            return False
        if self.capacity == self.occupied:
            return False
        is_leaf = not(self.left or self.right)
        if is_leaf:
            self.occupied += 1
            return True

        if self.right:
            result = self.right.occupy(rightmost_idx)
            if result:
                self.occupied += 1
                return True

        result = self.left.occupy(rightmost_idx)
        if result:
            self.occupied += 1
            return True
        return False


def buildtree(size):
    row = [SegmentNode(i, i, 1, 0, None, None) for i in range(size)]

    while len(row) > 1:
        newrow = []
        for i in range(0, len(row), 2):
            left = row[i]
            right = row[i + 1] if i + 1 < len(row) else None
            minidx = left.minidx
            maxidx = left.maxidx
            capacity = left.capacity
            if right:
                maxidx = right.maxidx
                capacity += right.capacity
            newrow.append(SegmentNode(minidx, maxidx, capacity, 0, left, right))
        row = newrow

    return row[0]

# st = buildtree(5)
# print(st.occupy(2))
# # print(st.occupy(1))
# st.print_tree()

def solution():
    n = read_int()

    lefties = []
    righties = []

    total = 0

    for _ in range(n):
        k, l, r = read_int_array()
        total += min(l, r)
        if l > r:
            lefties.append(Camel(k - 1, l - r))
        if r > l:
            righties.append(Camel(k - 1, r - l))

    lefties = sorted(lefties, key = lambda c: -c.v)
    righties = sorted(righties, key = lambda c: -c.v)

    ltree = buildtree(len(lefties))
    rtree = buildtree(len(righties))

    for l in lefties:
        if ltree.occupy(l.k):
            total += l.v

    for r in righties:
        if rtree.occupy(n - r.k - 2):
            total += r.v

    return total




def main():
    t = read_int()

    for i in range(t):
        s = solution()
        print(s)


main()


# ss = buildtree(100_000)
#
# for i in range(50000):
#     ss.occupy(50000)
#

Submission status: Runtime Error

Solution code:
from collections import namedtuple
from pprint import pp

Camel = namedtuple("Camel", "k v".split(" "))
def read_int():
    return int(input())

def read_int_array():
    return [int(ss) for ss in input().split()]

class SegmentNode:
    def __init__(self, minidx, maxidx, capacity, occupied, left, right):
        self.minidx = minidx
        self.maxidx = maxidx
        self.capacity = capacity
        self.occupied = occupied
        self.left = left
        self.right = right

    def __repr__(self):
        return f"[{self.minidx}-{self.maxidx}, {self.occupied}/{self.capacity}]"

    def print_tree(self, lvl = 0):
        print((" " * lvl) + self.__repr__())
        if self.left:
            self.left.print_tree(lvl + 2)
        if self.right:
            self.right.print_tree(lvl + 2)

    def occupy(self, rightmost_idx):
        if self.minidx > rightmost_idx:
            return False
        if self.capacity == self.occupied:
            return False
        is_leaf = not(self.left or self.right)
        if is_leaf:
            self.occupied += 1
            return True

        if self.right:
            result = self.right.occupy(rightmost_idx)
            if result:
                self.occupied += 1
                return True

        result = self.left.occupy(rightmost_idx)
        if result:
            self.occupied += 1
            return True
        return False


def buildtree(size):
    row = [SegmentNode(i, i, 1, 0, None, None) for i in range(size)]

    while len(row) > 1:
        newrow = []
        for i in range(0, len(row), 2):
            left = row[i]
            right = row[i + 1] if i + 1 < len(row) else None
            minidx = left.minidx
            maxidx = left.maxidx
            capacity = left.capacity
            if right:
                maxidx = right.maxidx
                capacity += right.capacity
            newrow.append(SegmentNode(minidx, maxidx, capacity, 0, left, right))
        row = newrow

    return row[0]

# st = buildtree(5)
# print(st.occupy(2))
# # print(st.occupy(1))
# st.print_tree()

def solution():
    n = read_int()

    lefties = []
    righties = []

    total = 0

    for _ in range(n):
        k, l, r = read_int_array()
        total += min(l, r)
        if l > r:
            lefties.append(Camel(k - 1, l - r))
        if r > l:
            righties.append(Camel(k - 1, r - l))

    lefties = sorted(lefties, key = lambda c: -c.v)
    righties = sorted(righties, key = lambda c: -c.v)

    ltree = buildtree(len(lefties))
    rtree = buildtree(len(righties))

    for l in lefties:
        if ltree.occupy(l.k):
            total += l.v

    for r in righties:
        if rtree.occupy(n - r.k - 2):
            total += r.v

    return total




def main():
    t = read_int()

    for i in range(t):
        s = solution()
        print(s)


main()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush, heapify

T = int(input())

for _ in range(T):
    N = int(input())
    camel = [tuple(map(int, input().split())) for i in range(N)]
    dif = [(camel[i][1] - camel[i][2], camel[i][0] - 1, i) for i in range(N)]

    pos = []
    neg = []

    for i in range(N):
        if dif[i][0] >= 0:
            pos.append((-dif[i][0], dif[i][1], dif[i][2]))
        else:
            neg.append(dif[i])

    p = len(pos)
    n = len(neg)

    pos.sort(key=lambda x: x[1], reverse=True)
    neg.sort(key=lambda x: x[1])

    heappos = []
    heapneg = []

    arr = [None for i in range(N)]

    j = 0
    for i in range(p)[::-1]:
        f = False
        while j != p and pos[j][1] >= i:
            heappush(heappos, pos[j])
            j += 1
            f = True
        #if not f and j != p:
        #    heappush(heappos, pos[j])
        #    j += 1
        d, k, id = heappop(heappos)
        arr[i] = id

    j = 0
    for i in range(n):
        f = False
        while j != n and neg[j][1] <= p + i:
            heappush(heapneg, neg[j])
            j += 1
            f = True
        #if not f and j != n:
        #    heappush(heapneg, neg[j])
        #    j += 1
        d, k, id = heappop(heapneg)
        arr[p + i] = id
    res = 0

    for i in range(N):
        k, l, r = camel[arr[i]]
        if k >= i + 1:
            res += l
        else:
            res += r

    print(res)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush, heapify

T = int(input())

for _ in range(T):
    N = int(input())
    camel = [tuple(map(int, input().split())) for _ in range(N)]
    dif = [(camel[i][1] - camel[i][2], camel[i][0] - 1, i) for i in range(N)]
    pos = []
    neg = []
    for i in range(N):
        if dif[i][0] >= 0:
            pos.append((-dif[i][0], dif[i][1], dif[i][2]))
        else:
            neg.append(dif[i])

    p = len(pos)
    n = len(neg)

    pos.sort(key=lambda x: x[1], reverse=True)
    neg.sort(key=lambda x: x[1])

    heappos = []
    heapneg = []

    arr = [None for _ in range(N)]

    j = 0
    f = False
    for i in range(p)[::-1]:
        while j != p and pos[j][1] >= i:
            heappush(heappos, pos[j])
            j += 1
            f = True
        if not f and j != p:
            heappush(heappos, pos[j])
            j += 1
        d, k, id = heappop(heappos)
        arr[i] = id

    j = 0
    f = False
    for i in range(n):
        while j != n and neg[j][1] <= N - i - 1:
            heappush(heapneg, neg[j])
            j += 1
            f = True
        if not f and j != n:
            heappush(heapneg, neg[j])
            j += 1
        d, k, id = heappop(heapneg)
        arr[N - 1 - i] = id

    res = 0

    for i in range(N):
        k, l, r = camel[arr[i]]
        if k <= i:
            res += r
        else:
            res += l

    print(res)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush, heapify

T = int(input())

for _ in range(T):
    N = int(input())
    camel = [tuple(map(int, input().split())) for _ in range(N)]
    dif = [(camel[i][1] - camel[i][2], camel[i][0] - 1, i) for i in range(N)]
    pos = []
    neg = []
    for i in range(N):
        if dif[i][0] >= 0:
            pos.append((-dif[i][0], dif[i][1], dif[i][2]))
        else:
            neg.append(dif[i])

    p = len(pos)
    n = len(neg)

    pos.sort(key=lambda x: x[1], reverse=True)
    neg.sort(key=lambda x: x[1])

    heappos = []
    heapneg = []

    arr = [None for _ in range(N)]

    j = 0
    f = False
    for i in range(p)[::-1]:
        while j != p and pos[j][1] >= i:
            heappush(heappos, pos[j])
            j += 1
            f = True
        if not f and j != p:
            heappush(heapneg, pos[j])
            j += 1
        d, k, id = heappop(heappos)
        arr[i] = id

    j = 0
    f = False
    for i in range(n):
        while j != n and neg[j][1] <= N - i - 1:
            heappush(heapneg, neg[j])
            j += 1
            f = True
        if not f and j != n:
            heappush(heapneg, neg[j])
            j += 1
        d, k, id = heappop(heapneg)
        arr[N - 1 - i] = id

    res = 0

    for i in range(N):
        k, l, r = camel[arr[i]]
        if k <= i:
            res += r
        else:
            res += l

    print(res)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush, heapify

T = int(input())

for _ in range(T):
    N = int(input())
    camel = [tuple(map(int, input().split())) for _ in range(N)]
    dif = [(camel[i][1] - camel[i][2], camel[i][0] - 1, i) for i in range(N)]
    pos = []
    neg = []
    for i in range(N):
        if dif[i][0] >= 0:
            pos.append((-dif[i][0], dif[i][1], dif[i][2]))
        else:
            neg.append(dif[i])

    p = len(pos)
    n = len(neg)

    pos.sort(key=lambda x: x[1], reverse=True)
    neg.sort(key=lambda x: x[1])

    heappos = []
    heapneg = []

    arr = [None for _ in range(N)]

    j = 0
    for i in range(p)[::-1]:
        while j != p and pos[j][1] >= i:
            heappush(heappos, pos[j])
            j += 1
        d, k, id = heappop(heappos)
        arr[i] = id

    j = 0
    for i in range(n):
        while j != n and neg[j][1] <= N - i - 1:
            heappush(heapneg, neg[j])
            j += 1
        d, k, id = heappop(heapneg)
        arr[N - 1 - i] = id

    res = 0

    for i in range(N):
        k, l, r = camel[arr[i]]
        if k <= i:
            res += r
        else:
            res += l

    print(res)

Submission status: Runtime Error

Solution code:
import sys
from heapq import *
readline = sys.stdin.readline

def solve2(left):
    ans = 0
    k2values = {}
    for v, k in left:
        if k not in k2values:
            k2values[k] = []
        k2values[k].append(v)
    
    pq = []
    maxk = max(k for v,k in left)
    for k in range(maxk, 0, -1):
        if k in k2values:
            for v in k2values[k]:
                heappush(pq, -v)
        if len(pq) > 0:
            v = heappop(pq)
            ans += -v
    return ans


def solve():
    N = int(readline())
    
    left = []
    right = []
    
    ans = 0
    
    for i in range(N):
        k, l, r = map(int, readline().split())
        if l > r:
            left.append((l - r, k))
            ans += r
        else:
            right.append((r - l, N - k))
            ans += l
    
    ans += solve2(left)
    ans += solve2(right)
    
    print(ans)

T = int(readline())
for i in range(T):
    solve()

Submission status: Runtime Error

Solution code:
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]=len(hL)-1:
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif R[i][0]==len(hR)-1:
            heapq.heappushpop(hR,R[i][1])
    print(ans+sum(hL)+sum(hR))

Submission status: Runtime Error

Solution code:
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]=len(hL)-1:
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif R[i][0]==len(hR)-1:
            heapq.heappushpop(hR,R[i][1])
    print(ans-sum(hL)-sum(hR))

Submission status: Runtime Error

Solution code:
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,-dif))
            ans+=ri
        else:
            R.append((n-ki-1,dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]==len(hL):
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>len(hR):
            heapq.heappush(hR,R[i][1])
        elif L[i][0]==len(hR):
            heapq.heappushpop(hR,R[i][1])
    print(ans-sum(hL)-sum(hR))

Submission status: Runtime Error

Solution code:
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]==len(hL)-1:
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif L[i][0]==len(hR)-1:
            heapq.heappushpop(hR,R[i][1])
    print(ans+sum(hL)+sum(hR))

Submission status: Runtime Error

Solution code:
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]==len(hL):
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif L[i][0]==len(hR):
            heapq.heappushpop(hR,R[i][1])
    print(ans+sum(hL)+sum(hR))