Problem:


Score : 800 points

Problem Statement

There are N positive integers A_1, A_2, ..., A_N.
Takahashi can perform the following operation on these integers any number of times:

Choose 1 \leq i \leq N and multiply the value of A_i by -2.

Notice that he multiplies it by minus two.

He would like to make A_1 \leq A_2 \leq ... \leq A_N holds.
Find the minimum number of operations required. If it is impossible, print -1.

Constraints

1 \leq N \leq 200000

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the answer.

Sample Input 1

4
3 1 4 1

Sample Output 1

3

One possible solution is:

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now 3, 1, 4, -2.

Choose i=1 and multiply the value of A_1 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, -2.

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, 4.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

0

A_1 \leq A_2 \leq ... \leq A_N holds before any operation is performed.

Sample Input 3

8
657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097

Sample Output 3

7



Sample input:
4
3 1 4 1


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import collections
import math


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

    lft = 0
    rgt = n
    while rgt - lft > 2:
        mi1 = (lft * 2 + rgt) // 3
        mi2 = (lft + rgt * 2) // 3
        ret1 = eval(a, mi1)
        ret2 = eval(a, mi2)
        if ret1 < ret2:
            rgt = mi2
        else:
            lft = mi1

    hoge = [eval(a, i) for i in range(lft, min([lft + 3, n]))]
    # hoge = [eval(a, i) for i in range(n)]
    print(min(hoge) if hoge else eval(a, n - 1))

def eval(a, m):
    ret = m
    if m > 0:
        tmp = a[m - 1]
        kata = 0
        for i in range(m - 1, 0, -1):
            if a[i - 1] < tmp:
                cnt = math.ceil(math.log(tmp / a[i - 1], 4))
                ret += cnt * 2 + kata
                tmp = a[i - 1] * 4 ** cnt
                if tmp > 1<<30:
                    hoge = int(math.log(tmp >> 30, 2))
                    hoge -= hoge % 2
                    kata += hoge
                    tmp >>= hoge
            else:
                tmp = a[i - 1]

    tmp = a[m]
    kata = 0
    for i in range(m + 1, len(a)):
        if a[i] < tmp:
            cnt = math.ceil(math.log(tmp / a[i], 4))
            if cnt < -1:
                return -1
            ret += cnt * 2 + kata
            tmp = a[i] * 4 ** cnt
            if tmp > 1<<30:
                hoge = int(math.log(tmp >> 30, 2))
                hoge -= hoge % 2
                kata += hoge
                tmp >>= hoge
        else:
            tmp = a[i]

    return ret


main()

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
log2 = {}
for a in A:
  log2[a] = math.log(a, 2)
# k個目を固定すると仮定したときの操作回数
def process(A, k):
  left = 0
  t = A[k]
  for i in range(k-1, -1, -1):
    a = A[i]
    if a > t:
      if t > 0:
        left += 1
        t = a * (-2)
      else:
        abst = abs(t)
        if abst not in log2:
          log2[abst] = math.log(abst, 2)
        l = math.ceil(log2[abst] - log2[a])
        if l % 2 == 0:
          l += 1 # 奇数にする
        left += l
        t = -(a * 2 ** l)
    else:
      t = a
  right = 0
  t = A[k]
  for i in range(k+1, N):
    a = A[i]
    if t > a:
      if t not in log2:
        log2[t] = math.log(t, 2)
      l = math.ceil(log2[t] - log2[a])
      if l % 2 == 1:
        l += 1 # 偶数にする
      right += l
      t = a * 2 ** l
    else:
      t = a
  return left + right

# 3分探索
fr = 0
to = N
while to - fr > 2:
  mid1 = fr + ((to - fr)) // 3
  mid2 = fr + ((to - fr) * 2) // 3
  if process(A, mid1) < process(A, mid2):
    to = mid2
  else:
    fr = mid1
print(min(process(A, fr), process(A, fr+1)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict
import bisect

N = int(input())
A = [int(x) for x in input().split()]


def f(A, fixIdx, m):
    r = 0
    for i in range(fixIdx - 1, -1, -1):
        if i + 1 < N:
            while A[i] > A[i + 1]:
                A[i] *= -2
                r += 1
                if A[i] == 0:
                    return INF
                if r >= m:
                    return INF

    for i in range(fixIdx + 1, len(A), 1):
        if i - 1 >= 0:
            while A[i - 1] > A[i]:
                A[i] *= -2
                r += 1
                if A[i] == 0:
                    return INF
                if r >= m:
                    return INF

    return r


INF = 10 ** 100
mi = INF

findZero = False
lastA = INF
for a in A:
    if findZero == True and a == 0 and lastA != 0:
        print(-1)
        sys.exit()
    if a == 0:
        findZero = True
    lastA = a

mIdx = []
miA = INF
for i in range(N):
    if miA == abs(A[i]):
        mIdx.append(i)
    elif miA > abs(A[i]):
        miA = abs(A[i])
        mIdx = [i]

for i in mIdx:
    AA = A.copy()
    tmp = f(AA, i, mi)
    mi = min(mi, tmp)

# for i in range(N):
#     AA = A.copy()
#     tmp = f(AA, i, mi)
#     mi = min(mi, tmp)


if mi == INF:
    print(-1)
else:
    print(mi)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict
import bisect

N = int(input())
A = [int(x) for x in input().split()]


def f(A, fixIdx, m):
    r = 0
    for i in range(fixIdx - 1, -1, -1):
        if i + 1 < N:
            while A[i] > A[i + 1]:
                A[i] *= -2
                r += 1
                if A[i] == 0:
                    return INF
                if r >= m:
                    return INF

    for i in range(fixIdx + 1, len(A), 1):
        if i - 1 >= 0:
            while A[i - 1] > A[i]:
                A[i] *= -2
                r += 1
                if A[i] == 0:
                    return INF
                if r >= m:
                    return INF

    return r


INF = 10 ** 100
mi = INF

findZero = False
lastA = INF
for a in A:
    if findZero == True and a == 0 and lastA != 0:
        print(-1)
        sys.exit()
    if a == 0:
        findZero = True
    lastA = a

mIdx = []
miA = INF
for i in range(N):
    if miA == A[i]:
        mIdx.append(i)
    elif miA > A[i]:
        miA = A[i]
        mIdx = [i]

for i in mIdx:
    AA = A.copy()
    tmp = f(AA, i, mi)
    mi = min(mi, tmp)

# for i in range(N):
#     AA = A.copy()
#     tmp = f(AA, i, mi)
#     mi = min(mi, tmp)


if mi == INF:
    print(-1)
else:
    print(mi)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
# k個目を固定すると仮定したときの操作回数
def process(A, k):
  left = 0
  t = A[k]
  for i in range(k-1, -1, -1):
    a = A[i]
    if a > t:
      if t > 0:
        left += 1
        t = a * (-2)
      else:
        l = math.ceil(math.log(abs(t), 2) - math.log(abs(a), 2))
        if l % 2 == 0:
          l += 1 # 奇数にする
        left += l
        t = -(a * 2 ** l)
    else:
      t = a
  right = 0
  t = A[k]
  for i in range(k+1, N):
    a = A[i]
    if t > a:
      l = math.ceil(math.log(abs(t), 2) - math.log(abs(a), 2))
      if l % 2 == 1:
        l += 1 # 偶数にする
      right += l
      t = a * 2 ** l
    else:
      t = a
  return left + right

# 3分探索
fr = 0
to = N
while to - fr > 2:
  mid1 = fr + ((to - fr)) // 3
  mid2 = fr + ((to - fr) * 2) // 3
  if process(A, mid1) < process(A, mid2):
    to = mid2
  else:
    fr = mid1
print(min(process(A, fr), process(A, fr+1)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

N = int(input())
A = list(map(int,input().split()))

ans_ans = -1
for i in range(N+1):
    ans = 0
    A_nega = A[:i]
    A_posi = A[i:]
    # print(A_nega,A_posi)
    prev = 0
    for a in reversed(A_nega):
        tmp = 0
        tmp_a = a
        while (a > prev):
            a *= -2
            tmp += 1
        ans += tmp
        prev = a
        
    prev = 0
    for a in A_posi:
        tmp = 0
        tmp_a = a
        while (a < prev):
            a *= -2
            tmp += 1
        ans += tmp
        prev = a
    # print(ans)
    if ans_ans == -1:
        ans_ans = ans
    else:
        ans_ans = min(ans_ans,ans)
    # print(ans_ans)
        
print(ans_ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
# k個目を固定すると仮定したときの操作回数
def process(A, k):
  left = 0
  t = A[k]
  for i in range(k-1, -1, -1):
    a = A[i]
    if a > t:
      if t > 0:
        left += 1
        t = a * (-2)
      else:
        l = math.ceil(math.log2(abs(t)) - math.log2(abs(a)))
        if l % 2 == 0:
          l += 1 # 奇数にする
        left += l
        t = -(a * 2 ** l)
    else:
      t = a
  right = 0
  t = A[k]
  for i in range(k+1, N):
    a = A[i]
    if t > a:
      l = math.ceil(math.log2(abs(t)) - math.log2(abs(a)))
      if l % 2 == 1:
        l += 1 # 偶数にする
      right += l
      t = a * 2 ** l
    else:
      t = a
  return left + right

# 3分探索
fr = 0
to = N
while to - fr > 2:
  mid1 = fr + ((to - fr)) // 3
  mid2 = fr + ((to - fr) * 2) // 3
  if process(A, mid1) < process(A, mid2):
    to = mid2
  else:
    fr = mid1
print(min(process(A, fr), process(A, fr+1)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int,input().split(" ")))
dp=[]
for i in range(0,n):
  dp.append([])
INF = 1;
for i in range(0,129):
  #print(str(i) + " " + str(INF))
  INF=INF*2
for i in range(0,n):
  for j in range(0,129):
    dp[i].append(INF)
for i in range(0,129):
  dp[0][i]=i
for i in range(1,n):
  cur = a[i];
  for j in range(0,129):
    cmpp = a[i-1]
    for k in range(0,129):
      if(cur>=cmpp):
        dp[i][j]=min(dp[i][j],dp[i-1][k]+j)
      cmpp*=-2
    cur*=-2

ans = INF
for i in range(0,129):
  ans=min(ans,dp[n-1][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict
import bisect

N = int(input())
A = [int(x) for x in input().split()]


def f(A, fixIdx, m):
    r = 0
    for i in range(fixIdx - 1, -1, -1):
        if i + 1 < N:
            while A[i] > A[i + 1]:
                A[i] *= -2
                r += 1
                if A[i] == 0:
                    return INF
                if r >= m:
                    return INF

    for i in range(fixIdx + 1, len(A), 1):
        if i - 1 >= 0:
            while A[i - 1] > A[i]:
                A[i] *= -2
                r += 1
                if A[i] == 0:
                    return INF
                if r >= m:
                    return INF

    return r


INF = 10 ** 100
mi = INF

findZero = False
lastA = INF
for a in A:
    if findZero == True and a == 0 and lastA != 0:
        print(-1)
        sys.exit()
    if a == 0:
        findZero = True
    lastA = a


for i in range(N):
    AA = A.copy()
    tmp = f(AA, i, mi)
    mi = min(mi, tmp)


if mi == INF:
    print(-1)
else:
    print(mi)

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil


def _check(bbb):
    ret = 0
    pb = -1
    for b in bbb:
        if pb > b:
            d = ceil((pb - b) / 2) * 2
            ret += d
            b += d
        pb = b
    return ret


def check(x, bbb):
    ret = x
    ret += _check(bbb[x:])
    ret += _check(reversed(bbb[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    bbb = list(map(log2, aaa))
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, bbb)
        res2 = check(m2, bbb)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m1 + 1
        else:
            r = m1
    return check(r, bbb)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict
import bisect

N = int(input())
A = [int(x) for x in input().split()]


def f(A, fixIdx):
    r = 0
    for i in range(fixIdx - 1, -1, -1):
        if i + 1 < N:
            while A[i] > A[i + 1]:
                A[i] *= -2
                r += 1
                if A[i] == 0:
                    return INF
    for i in range(fixIdx + 1, len(A), 1):
        if i - 1 >= 0:
            while A[i - 1] > A[i]:
                A[i] *= -2
                r += 1
                if A[i] == 0:
                    return INF

    return r


INF = 10**100
mi = INF


findZero = False
lastA = INF
for a in A:
    if findZero == True and a == 0 and lastA != 0:
        print(-1)
        sys.exit()
    if a == 0:
        findZero = True
    lastA = a


for i in range(N):
    AA = A.copy()
    mi = min(mi,f(AA, i))


if mi == INF:
    print(-1)
else:
    print(mi)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict
import bisect

N = int(input())
A = [int(x) for x in input().split()]


def f(A, fixIdx):
    r = 0
    for i in range(fixIdx - 1, -1, -1):
        if i + 1 < N:
            while A[i] > A[i + 1]:
                A[i] *= -2
                r += 1
    for i in range(fixIdx + 1, len(A), 1):
        if i - 1 >= 0:
            while A[i - 1] > A[i]:
                A[i] *= -2
                r += 1
    return r


mi = 10**100
for i in range(N):
    AA = A.copy()
    mi = min(mi,f(AA, i))
  

print(mi)

Submission status: Time Limit Exceeded

Solution code:
def do_sub(A):
    if len(A) <= 1: return 0

    N = len(A)
    res = 0
    for i in range(1, N):
        if A[i-1] <= A[i]: continue
        d = (A[i-1]+A[i]-1)//A[i]
        if (d & (d-1)) != 0:
            d <<= 1

        bl = d.bit_length() // 2 * 2
        res += bl
        A[i] <<= bl

    return res

def do(A, k):
    # [:k]: negative
    # [k:]: positive
    res = k
    res += do_sub([2*ai for ai in A[:k]][::-1])
    res += do_sub(A[k:])
    return res

def main():
    N = int(input())
    A = list(map(int, input().split()))

    if A == sorted(A):
        print(0)
        return 0

    lb, ub = 0, N
    res = 1e308
    while ub-lb > 1:
        mid = (lb+ub) >> 1
        left = do(A, mid)
        right = do(A, mid+1)
        res = min(res, left, right)
        if left < right:
            ub = mid
        else:
            lb = mid

    print(res)
    return 0

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
num = float("inf")
for i in range(N):
    tmp = 0
    pre = A[i]
    for j in range(i + 1, N):
        q = A[j]
        while pre > q:
            q *= 4
            tmp += 2
        pre = q

    pre = A[i]
    for j in range(i - 1, -1, -1):
        q = A[j]
        if q > 0:
            q *= -2
            tmp += 1
        while pre < q:
            q *= 4
            tmp += 2
        pre = q

    num = min(tmp, num)

print(num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
num = float("inf")
for i in range(N):
    tmp = 0
    pre = A[i]
    for j in range(i + 1, N):
        q = A[j]
        while pre > q:
            q *= 4
            tmp += 2
        pre = q

    pre = A[i]
    for j in range(i - 1, -1, -1):
        q = A[j]
        while pre < q:
            q *= -2
            tmp += 1
        pre = q

    num = min(tmp, num)

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

#負にする個数で場合分け
ANS=float("inf")

for j in range(min(N,100)):

    ANSj=j
    AR=copy.copy(A)
    for i in range(j+1,N):
        while AR[i]<AR[i-1]:
            AR[i]*=4
            ANSj+=2

    for i in range(j-1,-1,-1):
        while AR[i]<AR[i+1]:
            AR[i]*=4
            ANSj+=2

    if ANS>ANSj:
        ANS=ANSj

    #print(AR,ANSj)

print(ANS)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
def sub(a, minus=False):
    m = 20
    inf = 10**15
    dp = [[inf]*m for _ in range(n)] # i以降、a[i]に4^jをかけたところからソート
    for j in range(m):
        dp[-1][j] = j
    for i in range(n-2, -1, -1):
        if a[i]>a[i+1]:
            v = 0
            ai = a[i]; ai1 = a[i+1]
            while ai>ai1:
                ai1 *= 4
                v += 1
            for j in range(m):
                if j+v<m:
                    dp[i][j] = j + dp[i+1][j+v]
                else:
                    dp[i][j] = j + dp[i+1][m-1] + (n-i-1)*(j+v-m+1)
        else:
            v = 0
            ai = a[i]; ai1 = a[i+1]
            while True:
                ai *= 4
                if ai<=ai1:
                    v += 1
                else:
                    break
            for j in range(m):
                dp[i][j] = j + dp[i+1][max(0, j-v)]
    if minus:
        ans = [(2*min(dp[i][j] for j in range(m))+(n-i)) for i in range(n)]
    else:
        ans = [2*min(dp[i][j] for j in range(m)) for i in range(n)]
    return ans
dp0 = sub(list(a))
dp1 = sub([item for item in a[::-1]], minus=True)[::-1]
dp0.append(0)
dp1.insert(0,0)
ans = min((dp0[i]+dp1[i]) for i in range(n+1))
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  ret = 0
  while x > y:
    y *= 4
    ret += 1
  return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(l-1,10**18)]
  for i in range(l-1)[::-1]:
    ret[i] = ret[i+1]
    if ls[i] <= ls[i+1]:
      d = d4(ls[i+1],ls[i])-1
      if d > 0:
        stack.append((i,d))
    else:
      d = d4(ls[i],ls[i+1])
      while d:
        idx,num = stack.pop()
        if d > num:
          ret[i] += (idx-i)*num
          d -= num
        else:
          ret[i] += (idx-i)*d
          num -= d
          d = 0
          if num:
            stack.append((idx,num))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] *= 2
  cn[i] += n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(reversed(a))
c = [0] * (n + 1)
d = [0] * (n + 1)
s = [(0, 10 ** 30)]
res = 0
for i in range(1, n):
    if a[i - 1] < a[i] * 4:
        t = a[i - 1]
        cnt = 0
        while t < a[i]:
            cnt += 1
            t *= 4
        while cnt > 0:
            idx, p = s.pop()
            if cnt >= p:
                res += p * (i - idx)
                cnt -= p
            else:
                res += cnt * (i - idx)
                s.append((idx, p - cnt))
                cnt = 0
    else:
        t = a[i]
        cnt = 0
        while a[i - 1] >= t * 4:
            t *= 4
            cnt += 1
        s.append((i, cnt))
    c[i + 1] = res
s = [(0, 10 ** 30)]
res = 0
for i in range(1, n):
    if b[i - 1] < b[i] * 4:
        t = b[i - 1]
        cnt = 0
        while t < b[i]:
            cnt += 1
            t *= 4
        while cnt > 0:
            idx, p = s.pop()
            if cnt >= p:
                res += p * (i - idx)
                cnt -= p
            else:
                res += cnt * (i - idx)
                s.append((idx, p - cnt))
                cnt = 0
    else:
        t = b[i]
        cnt = 0
        while b[i - 1] >= t * 4:
            t *= 4
            cnt += 1
        s.append((i, cnt))
    d[i + 1] = res
ans = float('inf')
for i in range(n + 1):
    ans = min(ans, (c[i] + d[n - i]) * 2 + i)
print(ans)

Submission status: Accepted

Solution code:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
INF = 10**10
n = int(input())
a = list(map(int, input().split()))

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	if a[i-1] < a[i]:
		k = 0
		while a[i-1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_fr[i][j] = 2*j + dp_fr[i-1][j+k]
			else:
				dp_fr[i][j] = 2*j + dp_fr[i-1][19] + 2*(i) * (j+k-19)
	else:
		k = 0
		while a[i-1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j-k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	if a[i+1] < a[i]:
		k = 0
		while a[i+1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_ba[i][j] = 2*j + dp_ba[i+1][j+k]
			else:
				dp_ba[i][j] = 2*j + dp_ba[i+1][19] + 2*(n-i-1) * (j+k-19)
	else:
		k = 0
		while a[i+1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j-k, 0)]

#print(*dp_fr, sep="\n")
#print(*dp_ba, sep="\n")

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    def f(a, b):
        ret = 0
        while a > b:
            ret += 2
            b *= 4
        return ret

    N = int(input())
    A = list(map(int, input().split()))

    right = [0] * (N+1)
    st = [(1, A[-1], A[-1])]
    for i in range(N-2, -1, -1):
        a = A[i]
        st.append((1, a, a))
        right[i] = right[i+1]
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                right[i] += nb * k
                if st:
                    st.append((na+nb, amin, bmax << k))
                else:
                    st.append((na+nb, amin, float("inf")))
            else:
                break
    left = [0] * (N+1)
    left[1] = 1
    st = [(1, A[0], A[0])]
    for i in range(2, N+1):
        a = A[i-1]
        st.append((1, a, a))
        left[i] = left[i-1] + 1
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                left[i] += nb * k
                if st:
                    st.append((na + nb, amin, bmax << k))
                else:
                    st.append((na+nb, amin, float("inf")))
            else:
                break
    ans = float("inf")
    for i in range(N+1):
        ans = min(ans, left[i] + right[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    # result[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    # 第2項は巨大になり得るが、A_iの最大値 10^9 を超えたら常に末尾までが支配区間となるので、適当に上限でclip
    stack = [(10 ** 12, 10 ** 12, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 11
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Accepted

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))