Problem p02686 (python)

Fixed submission:
def main():
    import queue
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))



    n = int(input())
    minsum = [None] * n # (min, sum)
    for i in range(n):
        tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
        c = 0
        m = 0
        for item in tmp:
            c += item
            m = min(c, m)
        minsum[i] = (m, sum(tmp))
    minsum.sort()

    if sum(item[1] for item in minsum)!=0:
        print("No")
    else:
        minsum1 = [item for item in minsum if item[1]>=0]
        minsum2 = [(item[0]-item[1], -item[1]) for item in minsum if item[1]<0]
        minsum2.sort()
        c = 0
        for m,s in minsum1[::-1]:
            if c+m>=0:
                c += s
            else:
                print("No")
                return
        c = 0
        for m,s in minsum2[::-1]:
            if c+m>=0:
                c+=s
            else:
                print("No")
                return
        print("Yes")
main()

Buggy submission (verdict: Runtime Error):
import bisect
import pdb
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



########################################
import math

class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : nより大きい最小の2のべき乗
        """
        self.num = 2**(int(math.log2(n))+1)
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            for i,item in enumerate(a):
                self.update(i,item)
        
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i + self.num - 1
        while k >= 0:
            if x>self.seg[k]:
                self.seg[k] = x
                k = (k-1)//2
            else:
                break
                
    def query(self,a,b,k=0,l=0,r=None,index=False):
        """query(a,b,0,0,num):[a,b)の最大値
        index==Trueのときインデックスも返す
        """
        if r is None:
            r = self.num

        if r <= a or b <= l:
            return (-float("inf"), None) if index else -float("inf")
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k)) if index else self.seg[k]
        else:
            return max(self.query(a,b,2*k+1,l,(l+r)//2, index=index),self.query(a,b,2*k+2,(l+r)//2,r, index=index))
    
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)


    ######################################################


n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()


seg = SegmentTree(n, [item[1] for item in minsum])

if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    for i in range(n):
        ind = bisect.bisect_right(minsum, (-c, -10**9))
        if ind==n:
            print("No")
            break
        s, ind2 = seg.query(ind, n, index=True)
        c += s
        seg.update(ind2, -10**9)
    else:
        print("Yes")

Buggy submission (verdict: Runtime Error):
import bisect
import pdb
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


########################################
import math

class SegmentTree:
    def __init__(self, n):
        """初期化
        num : nより大きい最小の2のべき乗
        """
        self.num = 2**(int(math.log2(n))+1)
        self.seg = [0] * (2*self.num-1)
        
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i + self.num - 1
        while k >= 0:
            if x>self.seg[k]:
                self.seg[k] = x
                k = (k-1)//2
            else:
                break
                
    def query(self,a,b,k=0,l=0,r=None,index=False):
        """query(a,b,0,0,num):[a,b)の最大値
        index==Trueのときインデックスも返す
        """
        if r is None:
            r = self.num

        if r <= a or b <= l:
            return (-float("inf"), None) if index else -float("inf")
        elif a <= l and r <= b:
            return self.seg[k], self._index(k) if index else self.seg[k]
        else:
            return max(self.query(a,b,2*k+1,l,(l+r)//2, index=index),self.query(a,b,2*k+2,(l+r)//2,r, index=index))
    
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)


    ######################################################


n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()


seg = SegmentTree(n)

if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    for i in range(n):
        ind = bisect.bisect_right(minsum, (-c, -10**9))
        if ind==n:
            print("No")
            break
        s, ind2 = seg.query(ind, n, index=True)
        c += s
        seg.update(ind2, -10**9)
    else:
        print("Yes")

Buggy submission (verdict: Runtime Error):

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()
if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while minsum:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    if not minsum:
        print("Yes")
    else:
#         minsum.sort(key=lambda x: x[1])
    #     print(minsum, c)
        i = len(minsum)-1
        update = False
        done = [False] * len(minsum)
        for i in range(len(minsum)):
            m, s = minsum[i]
            if s<0:
                continue
            if c+m>=0:
                c += s
                done[i] = True
        for i in range(len(minsum), -1, -1):
            if done[i]:
                continue
            m, s = minsum[i]
            if c+m>=0:
                c += s
            else:
                print("No")
                break
        else:
            print("Yes")

Buggy submission (verdict: Runtime Error):

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))




n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()
if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while True:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    minsum.sort(key=lambda x: x[1])
#     print(minsum, c)
    i = len(minsum)-1
    while minsum:
        m, s = minsum[i]
        if c+m>=0:
            minsum.pop(i)
            c += s
            i = len(minsum) - 1
        else:
            i -= 1
            if i<0:
                print("No")
                break
    else:
        print("Yes")

Buggy submission (verdict: Runtime Error):

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))




n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()

if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while True:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    minsum.sort(key=lambda x: x[1])
#     print(minsum, c)
    i = len(minsum)-1
    while minsum:
        m, s = minsum[i]
        if c+m>=0:
            minsum.pop(i)
            c += s
            i = len(minsum) - 1
        else:
            i -= 1
            if i<0:
                print("No")
                break
    else:
        print("Yes")

Buggy submission (verdict: Runtime Error):

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()

if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while True:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    minsum.sort(key=lambda x: x[1])
#     print(minsum, c)
    i = len(minsum)-1
    update = False
    while minsum:
        m, s = minsum[i]
        if c+m>=0:
            minsum.pop(i)
            update = True
            c += s
        i -= 1
        if i<0:
            if not update:
                print("No")
                break
            i = len(minsum) - 1
    else:
        print("Yes")