Problem p03202 (python)

Fixed submission:
import bisect
from collections import deque

"""
def pl(d,k):

    now = d
    ind = bisect.bisect_left(dlis,d)

    while ind > 0:
        dic[dlis[ind]] += 1

        if dic[dlis[ind]] // k == 0:
            dic[dlis[ind]] = 0
        else:
            break

        ind -= 1

    

def able(k):

    ndep = A[0]
    for i in range(len(dlis)):
        dic[dlis[i]] = 0

    for i in range(N-1):
        i += 1
        if ndep < A[i]:
            dic[A[i]] = 0
            ndep = A[i]
        else:
            ndep = A[i]
            pl(ndep,k)

    print (dic,k)
    if dic[dlis[0]] < k:
        return True
    else:
        return False

"""

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1
    

def able(k):

    nq = deque([0])
    num = deque([A[0]])

    for i in range(N-1):
        i += 1

        if A[i] > A[i-1]:
            if nq[-1] == 0:
                num[-1] += A[i] - A[i-1]
            else:
                nq.append(0)
                num.append(A[i] - A[i-1])

        else:

            if A[i] < A[i-1]:
                ds = A[i-1] - A[i]
                while len(num) > 0 and ds >= num[-1]:
                    nq.pop()
                    ds -= num[-1]
                    num.pop()
                if len(num) == 0:
                    return False
                num[-1] -= ds

            now = 0
            while len(nq) > 0 and nq[-1] == k-1:
                now += num[-1]
                nq.pop()
                num.pop()
            if len(nq) == 0:
                return False

            if num[-1] == 1:
                nq[-1] += 1
            else:
                num[-1] -= 1
                nq.append(nq[-1] + 1)
                num.append(1)

            if now > 0:
                nq.append(0)
                num.append(now)

        while len(nq) > 1 and nq[-1] == nq[-2]:
            num[-2] += num[-1]
            nq.pop()
            num.pop()
    
        #print (k,A[i])
        #print (nq)
        #print (num)
    return True

            


N = int(input())

A = list(map(int,input().split()))
A.append(1)

l = 0
r = N

while r - l != 1 :

    m = (l + r) // 2

    if able(m):
        r = m
    else:
        l = m

print (r)

Buggy submission (verdict: Runtime Error):
import bisect
from collections import deque

"""
def pl(d,k):

    now = d
    ind = bisect.bisect_left(dlis,d)

    while ind > 0:
        dic[dlis[ind]] += 1

        if dic[dlis[ind]] // k == 0:
            dic[dlis[ind]] = 0
        else:
            break

        ind -= 1

    

def able(k):

    ndep = A[0]
    for i in range(len(dlis)):
        dic[dlis[i]] = 0

    for i in range(N-1):
        i += 1
        if ndep < A[i]:
            dic[A[i]] = 0
            ndep = A[i]
        else:
            ndep = A[i]
            pl(ndep,k)

    print (dic,k)
    if dic[dlis[0]] < k:
        return True
    else:
        return False

"""

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1
    

def able(k):

    nq = deque([0])
    num = deque([A[0]])

    for i in range(N-1):
        i += 1

        if A[i] > A[i-1]:
            if nq[-1] == 0:
                num[-1] += 1
            else:
                nq.append(0)
                num.append(1)

        else:

            if A[i] < A[i-1]:
                ds = A[i-1] - A[i]
                while ds >= num[-1]:
                    nq.pop()
                    ds -= num[-1]
                    num.pop()
                num[-1] -= ds

            now = 0
            while len(nq) > 0 and nq[-1] == k-1:
                now += num[-1]
                nq.pop()
                num.pop()
            if len(nq) == 0:
                return False

            if num[-1] == 1:
                nq[-1] += 1
            else:
                num[-1] -= 1
                nq.append(nq[-1] + 1)
                num.append(1)

            if now > 0:
                nq.append(0)
                num.append(now)

    return True

            


N = int(input())

A = list(map(int,input().split()))
A.append(1)

l = 0
r = N

while r - l != 1 :

    m = (l + r) // 2

    if able(m):
        r = m
    else:
        l = m

print (r)