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:
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: Runtime Error

Solution code:
n = int(input())
x = list(input())
cnt = x.count("1")

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f


for i in range(n):
    y = x[:]
    if x[i] == "1":
        y[i] = "0"
        z = "".join(y)
        z = int(z, 2)
        z %= (cnt - 1)
        if z == 0:
            print(1)
        else:
            ans = 1
            while z > 0:
                z %= popcount(z)
                ans += 1
            print(ans)
    else:
        y[i] = "1"
        z = "".join(y)
        z = int(z, 2)
        z %= (cnt + 1)
        if z == 0:
            print(1)
        else:
            ans = 1
            while z > 0:
                z %= popcount(z)
                ans += 1
            print(ans)

Submission status: Runtime Error

Solution code:
# Fast IO (only use in integer input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

import heapq

T = int(input())
for _ in range(T):
    N = int(input())
    frontCamel = []
    backCamel = []
    indifferentCamel = []
    Happiness = 0
    for _ in range(N):
        k,l,r = map(int,input().split())
        if l > r:
            frontCamel.append((k,l-r))
            Happiness += r
        elif r > l:
            backCamel.append((N-k,r-l))
            Happiness += l
        else:
            indifferentCamel.append((k,0))
            Happiness += l
    frontQ = []
    backQ = []
    frontCamel.sort(key = lambda x:x[0])
    backCamel.sort(key = lambda x:x[0])
    for Camel in frontCamel:
        if Camel[0] == 0:
            continue
        if Camel[0] > len(frontQ):
            heapq.heappush(frontQ,Camel[1])
        else:
            if frontQ[0] < Camel[1]:
                heapq.heapreplace(frontQ,Camel[1])
    for Camel in backCamel:
        if Camel[0] == 0:
            continue
        if Camel[0] > len(backQ):
            heapq.heappush(backQ,Camel[1])
        else:
            if frontQ[0] < Camel[1]:
                heapq.heapreplace(backQ,Camel[1])
    Happiness += sum(frontQ)
    Happiness += sum(backQ)
    print(Happiness)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(N, K, L, R):
    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    score = 0
    for k, l, r in zip(K, L, R):
        k -= 1
        if l < r:
            score += l
            right[k].append(r - l)
        else:
            score += r
            left[k].append(l - r)
    q = []
    for n, xs in enumerate(left, 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    q = []
    for n, xs in enumerate(right[::-1][1:], 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    return score

T = int(readline())
for _ in range(T):
    N = int(readline())
    K, L, R = [], [], []
    for _ in range(N):
        k, l, r = map(int, readline().split())
        K.append(k)
        L.append(l)
        R.append(r)
    print(main(N, K, L, R))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
ones = 0
for i in x:
    if i=='1':
        ones += 1
mods = [0, 0]
for i in range(n):
    if x[n-i-1]=='1':
        if ones>1:
            mods[0] += pow(2, i, ones-1)
        mods[1] += pow(2, i, ones+1)
if ones>1:
    mods[0] %= ones-1
mods[1] %= ones+1
def f(x):
    if x==0:
        return 1
    cnt = 1
    while x>0:
        p = bin(x).count('1')
        x %= p
        cnt += 1
    return cnt
for i in range(n-1, -1, -1):
    if x[n-i-1]=='1' and ones==1:
        print(0)
        continue
    if x[n-i-1]=='1':
        init = (mods[0] - pow(2, i, ones-1))%(ones-1)
    else:
        init = (mods[1] + pow(2, i, ones+1))%(ones+1)
    print(f(init))

Submission status: Runtime Error

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


class TreapNode:
    """Treapのノード定義
    メンバ変数: 値、優先度、親へのポインタ、左右の子へのポインタ"""
    def __init__(self, val):
        self.val = val
        self.priority = random()
        self.parent, self.right, self.left = None, None, None


class Treap:
    """平衡二分探索木: 値の検索、挿入、削除などクエリ処理をO(logN)で実行する"""
    def __init__(self, is_multiset=False):
        self.is_multiset = is_multiset
        self.root = None

    def search(self, val: int) -> bool:
        """値の検索: 集合に値valを持つノードが存在するか"""
        ptr = self.root
        while ptr is not None:
            if val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                return True
        return False

    def insert(self, val: int) -> bool:
        """値の削除: 集合に値valを持つノードを挿入する"""
        if self.root is None:
            self.root = TreapNode(val)
            return True

        # ノードの挿入
        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    ptr.left = TreapNode(val)
                    ptr.left.parent = ptr
                    ptr = ptr.left
                    break
                ptr = ptr.left
            else:
                if val == ptr.val and not self.is_multiset:
                    return False
                elif ptr.right is None:
                    ptr.right = TreapNode(val)
                    ptr.right.parent = ptr
                    ptr = ptr.right
                    break
                ptr = ptr.right

        # 木の回転によってヒープ性を保つ
        while (ptr.parent is not None) and (ptr.parent.priority > ptr.priority):
            if ptr.parent.right == ptr:
                self._rotate_left(ptr.parent)
            else:
                self._rotate_right(ptr.parent)
        if ptr.parent is None:
            self.root = ptr 
        return True

    def delete(self, val: int) -> True:
        """値の削除: 集合から値valを持つノードを削除する"""
        if self.root is None:
            return False

        ptr = self.root         
        while True: 
            if ptr is None:
                return False
            elif val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                break

        # 木の回転によって削除したいノードを葉に持っていく
        while (ptr.left is not None) or (ptr.right is not None):
            if ptr.left is None:
                self._rotate_left(ptr)
            elif ptr.right is None:
                self._rotate_right(ptr)
            elif ptr.left.priority < ptr.right.priority:
                self._rotate_right(ptr)
            else:
                self._rotate_left(ptr)
            if self.root == ptr:
                self.root = ptr.parent

        # ノードの削除
        if ptr.left is None and ptr.right is None:
            if ptr == self.root:
                self.root = None
            elif ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None      
        return True

    def _rotate_left(self, ptr):
        """木の左回転を行う"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def _rotate_right(self, ptr):
        """木の右回転を行う"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def search_min(self):
        ptr = self.root
        ret = None
        while ptr is not None:
            ret = ptr.val
            ptr = ptr.left
        return ret

    def search_max(self):
        ptr = self.root
        ret = None
        while ptr is not None:
            ret = ptr.val
            ptr = ptr.right
        return ret

    def search_le(self, val: int):
        """val以下の最大の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val <= val:
                ret = ptr.val
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_lt(self, val: int):
        """valよりも小さいの最大の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val < val:
                ret = ptr.val
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_ge(self, val: int):
        """val以上の最小の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val >= val:
                ret = ptr.val
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret
      
    def search_gt(self, val: int):
        """valよりも大きい最小の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val > val:
                ret = ptr.val
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret


t = int(input())
for _ in range(t):
    n = int(input())
    info = [list(map(int, input().split())) for i in range(n)]
    li = []
    ans = 0
    p_cnt = 0
    m_cnt = 0
    for k, l, r in info:
        diff = l - r
        ans += r
        if diff > 0:
           p_cnt += 1
        if diff < 0:
           m_cnt += 1
        li.append((diff, k - 1))
        li = sorted(li, reverse=True)

    tp1 = Treap()
    tp2 = Treap()
    

    for i in range(p_cnt):
        tp1.insert(i)
    for i in range(n - m_cnt, n):
        tp2.insert(i)

    for diff, k in li:
        if diff > 0:
            ind = tp1.search_le(k)
            if ind <= k:
                tp1.delete(ind)
                ans += diff
        elif diff == 0:
            continue
        else:
            ind = tp2.search_gt(k)
            if ind is not None:
                tp2.delete(ind)
            else:
                ans += diff
    print(ans)