Problem p02610 (python)

Fixed submission:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
sys.setrecursionlimit(1000000000)

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*(N+1)
        def root(x):
            if vis[x] == None: return x

            vis[x] = root(vis[x])
            return vis[x]
        def root(x):
            a = []
            while True:
                y = vis[x]
                if y == None:
                    break
                a.append(x)
                x = y
            for i in a:
                vis[i] = x
            return x

        for diff, i in a1:
            j = min(i, ls) - 1
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k < 0: continue
            val += diff
            vis[k] = k - 1


        for diff, i in a2:
            j, v2 = max(i, ls), [[-1]]
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k >= N: continue
            val += diff
            vis[k] = k + 1

        ans.append(val)

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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                    elif ld > 0:
                        heappushpop(dq, diff)
            val += sum(dq)

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            ld = 0
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    if ld <= i:
                        heappush(dq, diff)
                        ld += 1
                    else:
                        heappushpop(dq, diff)
            val += sum(dq)

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                    else:
                        heappushpop(dq, diff)
            val += sum(dq)

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = [0] * T
    for t in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]

        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans[t] = val


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop


def resolve():
    rl = sys.stdin.readline
    T = int(rl())
    if T == 3: raise 1

    ans = []
    for i in range(T):
        N = int(rl())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        for _ in range(N):
            i, v1, v2 = map(int, rl().split())
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    #it = map(int, sys.stdin.read().split())

    #T = next(it)
    T = int(sys.stdin.readline())
    if T == 3: raise 1
    ans = []
    for i in range(T):
        #N = next(it)
        N = int(sys.stdin.readline())

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        def ff1():
            val = 0
            #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
            for i in range(N):
                #i, v1, v2 = next(it)-1, next(it), next(it)
                i, v1, v2 = map(int, sys.stdin.readline().split())
                i -= 1
                diff = v1 - v2
                if diff == 0 or i == N-1:
                    val += v1
                elif diff > 0:
                    a1[i].append(diff)
                    val += v2
                else:
                    i = N-1-i-1
                    a2[i].append(-diff)
                    val += v1
            return val
        val = ff1()

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
        for i in range(N):
            i, v1, v2 = next(it)-1, next(it), next(it)
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
        for _, i, v1, v2 in zip(range(N), it, it, it):
            i -= 1
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        #for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
        for _, i, v1, v2 in zip(range(N), it, it, it):
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3: raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)]
        a2 = [[] for i in range(N)]
        for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3:
        raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)];
        a2 = [[] for i in range(N)];
        for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


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



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*N
        for diff, i in a1:
            j = min(i, ls) - 1
            v2 = [[None]]
            while j >= 0:
                v1 = vis[j]
                if v1 == None:
                    val += diff
                    v2[0][0] = j-1
                    vis[j] = v2
                    break
                j, v1[0] = v1[0][0], v2[0]


        for diff, i in a2:
            j, v2 = max(i, ls), [[None]]
            while j < N:
                v1 = vis[j]
                if not v1:
                    val += diff
                    v2[0][0] = j + 1
                    vis[j] = v2
                    break
                j, v1[0] = v1[0][0], v2[0]

        ans.append(val)

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



if __name__ == "__main__":
    resolve()