Problem p03202 (python)

Fixed submission:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def shave(stack:list, nex:int, prv:int):
    res = prv-nex
    while res > 0:
        if res >= stack[-1][1]:
            _,y = stack.pop()
            res -= y
        else:
            stack[-1][1] -= res
            res = 0
            

def normalize(stack: list):
    if stack[-1][0] == stack[-2][0]:
        stack[-2][1] += stack[-1][1]
        stack.pop()
        
def add(stack:list):
    if stack[-1][1] == 1:
        stack[-1][0] += 1
    else:
        stack[-1][1] -= 1
        stack.append([stack[-1][0]+1, 1])
        
def kuriagari(stack:list):
    _, y = stack.pop()
    add(stack)
    normalize(stack)
    stack.append([1,y])
    
def check(a:list, upto:int):
    stack = [[0,0]]
    for i in range(n):
        if a[i+1] > a[i]:
            stack.append([1, a[i+1]-a[i]])
            normalize(stack)
        else:
            shave(stack, a[i+1], a[i])
            
            if stack[-1][0] == upto and stack[-1][1] == a[i+1]:
                return False

            elif stack[-1][0] == upto:
                kuriagari(stack)
            
            else:
                add(stack)
                normalize(stack)
                
    return True
   
    
def binsearch(a:list):
    low = 0
    high = 10**9+1
    
    while high-low > 1:
        mid = (high+low) // 2
        if check(a, mid):
            high = mid
        else:
            low = mid
            
    return high

n = ni()
a = [0] + list(li())
ans = binsearch(a)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
#stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def shave(stack:list, nex:int, prv:int):
    res = prv-nex
    while res > 0:
        if res >= stack[-1][1]:
            _,y = stack.pop()
            res -= y
        else:
            stack[-1][1] -= res
            res = 0
            

def normalize(stack: list):
    if stack[-1][0] == stack[-2][0]:
        stack[-2][1] += stack[-1][1]
        stack.pop()
        
def add(stack:list):
    if stack[-1][1] == 1:
        stack[-1][0] += 1
    else:
        stack[-1][1] -= 1
        stack.append([stack[-1][0]+1, 1])
        
def kuriagari(stack:list):
    _, y = stack.pop()
    stack[-1][0] += 1
    normalize(stack)
    stack.append([1,y])
    
def check(a:list, upto:int):
    stack = [[0,0]]
    for i in range(n):
        if a[i+1] > a[i]:
            stack.append([1, a[i+1]-a[i]])
            normalize(stack)
        else:
            shave(stack, a[i+1], a[i])
            
            if stack[-1][0] == upto and stack[-1][1] == a[i+1]:
                return False

            elif stack[-1][0] == upto:
                kuriagari(stack)
            
            else:
                add(stack)
                normalize(stack)
                
    return True
   
    
def binsearch(a:list):
    low = 0
    high = 10**9+1
    
    while high-low > 1:
        mid = (high+low) // 2
        if check(a, mid):
            high = mid
        else:
            low = mid
            
    return high

n = ni()
a = [0] + list(li())
ans = binsearch(a)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# 二分探索のTrue / False 判定関数
def check(k:int, a:list):
    # 最高の文字数
    ret = 1
    cur = 0
    
    # スタックを準備 文字列 "aab" を [[1,2], [2,1]]のように管理する
    stack = [[1, a[0]]]
    for i in range(len(a)-1):

        # a[i+1]の方が大きいならば末尾にaをa[i+1]-a[i]個だけ付ける
        if a[i+1] > a[i]:
            stack.append([1, a[i+1]-a[i]])
            
        # a[i+1]がa[i]以下ならばa[i+1]-1になるまで取り除く
        else:
            res = a[i] - (a[i+1]-1)
            while res > 0:
                if res >= stack[-1][1]:
                    x,y = stack.pop()
                    res -= y
                    cur = x+1
                    
                else:
                    stack[-1][1] -= res
                    res = max(0, res-stack[-1][1]) 
                    cur = stack[-1][0]+1
            
            stack.append([cur, 1])
            ret = max(ret, cur)
            
    if ret <= k:
        return True
    else:
        return False


# 二分探索関数
def binsearch(n:int, a: list):
    low = 0
    high = 10**9+1
    
    while high-low > 1:
        mid = (high+low) // 2
        if check(mid, a):
            high = mid
        else:
            low = mid
            
    return high


# 入力
n = ni()
a = list(li())

ans = binsearch(n,a)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# 二分探索のTrue / False 判定関数
def check(k:int, a:list):
    # 最高の文字数
    ret = 1
    
    # スタックを準備 文字列 "aab" を [[1,2], [2,1]]のように管理する
    stack = []
    for i in range(len(a)-1):
        if len(stack) == 0:
            stack.append([1, a[i]])
            
        elif a[i+1] > a[i]:
            stack.append([1, a[i+1]-a[i]])
            
        else:
            res = a[i] - (a[i+1]-1)
            while res > 0:
                if res >= stack[-1][1]:
                    x,y = stack.pop()
                    res -= y
                    cur = x+1
                else:
                    stack[-1][1] -= res
                    res = 0
                    cur = stack[-1][0]+1
                    
            stack.append([cur, 1])
            ret = max(ret, cur)
            
    if ret > k:
        return False
    else:
        return True


# 二分探索関数
def binsearch(n:int, a: list):
    low = 0
    high = 10**9+1
    
    while high-low > 1:
        mid = (high+low) // 2
        if check(mid, a):
            high = mid
        else:
            low = mid
            
    return high


# 入力
n = ni()
a = list(li())

ans = binsearch(n,a)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# 二分探索のTrue / False 判定関数
def check(k:int, a:list):
    # 最高の文字数
    ret = 1
    
    # スタックを準備 文字列 "aab" を [[1,2], [2,1]]のように管理する
    stack = []
    for i in range(len(a)-1):
        if len(stack) == 0:
            stack.append([1, a[i]])
            
        elif a[i+1] > a[i]:
            stack.append([1, a[i+1]-a[i]])
            
        else:
            res = a[i] - (a[i+1]-1)
            while res > 0:
                if res >= stack[-1][1]:
                    x,y = stack.pop()
                    res -= y
                    cur = x+1
                else:
                    stack[-1][1] -= res
                    res = 0
                    cur = stack[-1][0]+1
                    
            stack.append([cur, 1])
            ret = max(ret, cur)
            
    if ret > k:
        return False
    else:
        return True


# 二分探索関数
def binsearch(n:int, a: list):
    low = 0
    high = 10**9+1
    
    while high-low > 1:
        mid = (high+low) // 2
        if check(mid, a):
            high = mid
        else:
            low = mid
            
    return high


# 入力
n = ni()
a = list(li())

ans = binsearch(n,a)
print(ans)