Problem p03198 (python)

Fixed submission:
from collections import deque

n = int(input())
a = list(map(int,input().split()))

p = [0] * (n-1)
m = [0] * (n-1)

for i in range(n-1):
    x,y = a[i:i+2]
    cnt = 0
    if(x > y):
        while(x>y):
            y *= 4
            cnt += 2
    else:
        x *= 4
        while(x<=y):
            x*=4
            cnt -= 2
    p[i] = cnt

for i in range(n-1):
    x,y = a[i:i+2]
    cnt = 0
    if(x < y):
        while(x<y):
            x *= 4
            cnt += 2
    else:
        y *= 4
        while(x>=y):
            y*=4
            cnt -= 2
    m[i] = cnt

cumsum_p = [0] * (n+1)
cumsum_m = [0] * (n+1)

d = deque()
for i in range(n-2,-1,-1):
    cumsum_p[i] = cumsum_p[i+1]
    if(p[i] < 0):
        d.appendleft((i,p[i]))
    elif(p[i] > 0):
        cnt = p[i]
        while(d):
            j,rem_j = d.popleft()
            if(cnt + rem_j <= 0):
                cumsum_p[i] += (j-i) * cnt
                if(cnt + rem_j < 0):
                    d.appendleft((j,cnt + rem_j))
                cnt = 0
                break
            else:
                cumsum_p[i] += (j-i) * (-1 * rem_j)
                cnt = cnt + rem_j
        cumsum_p[i] += (n-i-1) * cnt

d = deque()
cumsum_m[1] = 1
for i in range(n-1):
    cumsum_m[i+2] = cumsum_m[i+1] + 1
    if(m[i] < 0):
        d.appendleft((i,m[i]))
    elif(m[i] > 0):
        cnt = m[i]
        while(d):
            j,rem_j = d.popleft()
            if( cnt + rem_j <= 0 ):
                cumsum_m[i+2] += (i-j) * cnt
                if( cnt + rem_j < 0):
                    d.appendleft((j,cnt + rem_j))
                cnt = 0
                break
            else:
                cumsum_m[i+2] += (i-j) * (-1*rem_j)
                cnt = cnt + rem_j
        cumsum_m[i+2] += (i+1) * cnt

ans = cumsum_p[0]
for i in range(n+1):
    ans = min(ans, cumsum_p[i] + cumsum_m[i])

print(ans)

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

n = int(input())
a = list(map(int,input().split()))

if(n==1):
    print(0)
    exit()

all_plus = [0] * n
all_minus = [0] * n

for i in range(1,n):
    cnt = 0
    if( a[i-1] <= a[i]):
        x = a[i-1] * 4
        while(x <= a[i]):
            x *= 4
            cnt -= 2
    else:
        x = a[i]
        while(a[i-1] > x):
            cnt += 2
            x *= 4
    all_plus[i-1] = cnt

for i in range(n-2,-1,-1):
    cnt = 0
    if( a[i] >= a[i+1]):
        x = a[i+1]*4
        while(a[i] >= x):
            x *= 4
            cnt -= 2
    else:
        x = a[i]
        while(x < a[i+1]):
            cnt += 2
            x *= 4
    all_minus[i] = cnt

cumsum_p = [0] * (n+1)
d = deque()
for i in range(n-2,-1,-1):
    cumsum_p[i] = cumsum_p[i+1]
    if(all_plus[i] < 0):
        d.appendleft((i,all_plus[i]))
    elif(all_plus[i] > 0):
        point = i
        cnt = all_plus[i]
        while(d):
            j,num_j = d.popleft()
            cumsum_p[i] += cnt * (j-point)
            point = j
            if(num_j + cnt < 0):
                d.appendleft(j,num_j+cnt)
                cnt = 0
                break
            else:
                cnt = num_j + cnt
        cumsum_p[i] += cnt * (n-point-1)

cumsum_m = [1] * (n)
d = deque()
for i in range(n-1):
    cumsum_m[i+1] = cumsum_m[i] + 1
    if(all_minus[i] < 0):
        d.appendleft((i,all_minus[i]))
    elif(all_minus[i] > 0):
        point = i+1
        cnt = all_minus[i]
        while(d):
            j,num_j = d.popleft()
            cumsum_m[i+1] += cnt * (point-j)
            point = j
            if(num_j + cnt < 0):
                d.appendleft(j,num_j+cnt)
                cnt = 0
                break
            else:
                cnt = num_j + cnt
        cumsum_m[i+1] += cnt * point
cumsum_m = [0] + cumsum_m

ans = min(cumsum_p[0], cumsum_m[-1])
for i in range(1,n):
    #minusの数がi個あるとする。
    tmp = cumsum_m[i] + cumsum_p[i]
    ans = min(ans,tmp)

print(ans)

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

n = int(input())
a = list(map(int,input().split()))

if(n==1):
    print(0)
    exit()

all_plus = [0] * n
all_minus = [0] * n

for i in range(1,n):
    cnt = 0
    if( a[i-1] <= a[i]):
        x = a[i-1] * 4
        while(x <= a[i]):
            x *= 4
            cnt -= 2
    else:
        x = a[i]
        while(a[i-1] > x):
            cnt += 2
            x *= 4
    all_plus[i] = cnt

for i in range(n-2,-1,-1):
    cnt = 0
    if( a[i] >= a[i+1]):
        x = a[i+1]*4
        while(a[i] >= x):
            x *= 4
            cnt -= 2
    else:
        x = a[i]
        while(x < a[i+1]):
            cnt += 2
            x *= 4
    all_minus[i] = cnt

cumsum_p = [0] * (n+1)
d = deque()
for i in range(n-1,0,-1):
    cumsum_p[i-1] = cumsum_p[i]
    if(all_plus[i] < 0):
        d.appendleft((i,all_plus[i]))
    elif(all_plus[i] > 0):
        point = i
        cnt = all_plus[i]
        while(d):
            j,num_j = d.popleft()
            cumsum_p[i-1] += cnt * (j-point)
            point = j
            if(num_j + cnt < 0):
                d.appendleft(j,num_j+cnt)
                cnt = 0
                break
            else:
                cnt = num_j + cnt
        cumsum_p[i-1] += cnt * (n-point)

cumsum_m = [1] * (n)
d = deque()
for i in range(n-1):
    cumsum_m[i+1] = cumsum_m[i] + 1
    if(all_minus[i] < 0):
        d.appendleft((i,all_minus[i]))
    elif(all_minus[i] > 0):
        point = i+1
        cnt = all_minus[i]
        while(d):
            j,num_j = d.popleft()
            cumsum_m[i+1] += cnt * (point-j)
            point = j
            if(num_j + cnt < 0):
                d.appendleft(j,num_j+cnt)
                cnt = 0
                break
            else:
                cnt = num_j + cnt
        cumsum_m[i+1] += cnt * point
cumsum_m = [0] + cumsum_m

ans = min(cumsum_p[0], cumsum_m[-1])
for i in range(1,n):
    #minusの数がi個あるとする。
    tmp = cumsum_m[i] + cumsum_p[i]
    ans = min(ans,tmp)

print(ans)