Problem:


Score : 600 points

Problem Statement

There are N cities in Republic of AtCoder. The size of the i-th city is A_{i}.
Takahashi would like to build N-1 bidirectional roads connecting two cities so that any city can be reached from any other city by using these roads.

Assume that the cost of building a road connecting the i-th city and the j-th city is |i-j| \times D + A_{i} + A_{j}.
For Takahashi, find the minimum possible total cost to achieve the objective.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq D \leq 10^9

1 \leq A_{i} \leq 10^9

A_{i} and D are integers.

Input

Input is given from Standard Input in the following format:

N D
A_1 A_2 ... A_N

Output

Print the minimum possible total cost.

Sample Input 1

3 1
1 100 1

Sample Output 1

106

This cost can be achieved by, for example, building roads connecting City 1, 2 and City 1, 3.

Sample Input 2

3 1000
1 100 1

Sample Output 2

2202

Sample Input 3

6 14
25 171 7 1 17 162

Sample Output 3

497

Sample Input 4

12 5
43 94 27 3 69 99 56 25 8 15 46 8

Sample Output 4

658



Sample input:
3 1
1 100 1


Sample output:
106

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.buffer.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 10**15
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index:
                index = (index - 1) >> 1
                L = self.seg_min[index * 2 + 1]
                R = self.seg_min[index * 2 + 2]
                if L < R:
                    self.seg_min[index] = L
                else:
                    self.seg_min[index] = R
                #self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret_new = self.seg_min[first]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret_new = self.seg_min[last]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[last])
                first = first >> 1
                last = (last >> 1) - 1
            return ret

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

    tmp = [(a, i+1) for i, a in enumerate(A)]
    #tmp.sort(key=lambda x: x[0])
    tmp.sort(key=itemgetter(0))
    segtree_plus = SegTree(N+5)
    segtree_minus = SegTree(N+5)
    edge = []
    val2idx_plus = {}
    val2idx_minus = {}
    edge_append = edge.append
    inf = 10**15
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(i, val_plus)
        segtree_minus.update(i, val_minus)
        if val_plus not in val2idx_plus:
            val2idx_plus[val_plus] = i
        else:
            i_ori = val2idx_plus[val_plus]
            if i > i_ori:
                val2idx_plus[val_plus] = i
        if val_minus not in val2idx_minus:
            val2idx_minus[val_minus] = i
        else:
            i_ori = val2idx_minus[val_minus]
            if i < i_ori:
                val2idx_minus[val_minus] = i
        plus_min = segtree_plus.query(i+1, N+2)
        if plus_min < inf:
            j_plus = val2idx_plus[plus_min]
            edge_append((i, j_plus, A[i-1] + A[j_plus-1] + D*(j_plus - i)))
        minus_min = segtree_minus.query(1, i-1)
        if minus_min < inf:
            j_minus = val2idx_minus[minus_min]
            edge_append((i, j_minus, A[i-1] + A[j_minus-1] + D * (i - j_minus)))

    #edge.sort(key=lambda x: x[2])
    edge.sort(key=itemgetter(2))
    UF = UnionFind(N + 1)
    ans = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
    print ans


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, D = mi()

#As[i] = [各都市のコスト,各都市の番号]
#0-indexed
As = [[a, i] for i, a in enumerate(list(mi()))]

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

#As_規模降順 = [各都市の規模, 各都市の番号（降順ソート前の番号）]
from operator import itemgetter
As_costdescending = sorted(As, key=itemgetter(0), reverse=True)

#SegTreeはやめて、累積最小値を使う
cummin_left = [0] * N
cummin_right = [0] * N

tmpmin = INF
tmpminidx = -1
for i in range(0, N-1): #leftなので、0~N-2を更新
  if (N-i)*D+As[i][0] <= tmpmin:
    tmpmin = (N-i)D+As[i][0]
    tmpminidx = i
  cummin_left[i] = tmpminidx

tmpmin = INF
tmpminidx = -1
for i in range(N-1, 0, -1): #rightなので、N-1~1を更新
#  print(i+As[i][0])
  if i*D+As[i][0] <= tmpmin:
    tmpmin = i*D+As[i][0]
    tmpminidx = i
  cummin_right[i] = tmpminidx

#print(cummin_left)
#print(cummin_right)
#[(cost, idx, adjidx), ...]
edge_candidates = []

for a, o_idx in As_costdescending: #o_idx:降順にする前のidx
  if o_idx == 0: #右だけを見る
    rightmin_oidx = cummin_right[1]
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))
  elif o_idx == N-1: #左だけを見る
    leftmin_oidx = cummin_left[N-2]
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
  else:
    leftmin_oidx = cummin_left[o_idx-1]
#    print('+0:', o_idx)
#    print('+1:', o_idx+1, cummin_right[o_idx+1])
    rightmin_oidx = cummin_right[o_idx+1]
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))


heapq.heapify(edge_candidates)

#上でできた配列に対してクラスカル法を適用して最小全域木（のコスト総和）を求める
#Union-Findを使ったクラスカル法
uf = UnionFind(N)
ans = 0
while edge_candidates:
  c, idx, adjidx = heapq.heappop(edge_candidates)
  if not uf.isSameGroup(idx, adjidx):
    ans += c
    uf.Unite(idx, adjidx)

print(ans)

Submission status: Runtime Error

Solution code:
from typing import Callable


def connecting_cities(N: int, D: int, A: list) -> int:
    edges = select_edges(N, D, A)
    edges = sorted(edges, key=lambda x: x[2], reverse=True)

    uft = UnionFindTree(N)

    count = 0
    while not len(edges) == 0:
        u, v, d = edges.pop()

        if not uft.same(u, v):
            uft.summarize(u, v)
            count += d

    return count


def select_edges(N: int, D: int, A: list) -> list:
    INF = 1 << 32
    st_l = SegmentTree(N, lambda x, y: x if x[0] < y[0] else y, (INF, -1))
    st_r = SegmentTree(N, lambda x, y: x if x[0] < y[0] else y, (INF, -1))
    indexes_A = sorted([i for i in range(N)], key=lambda x: A[x])

    edges = []
    for i in indexes_A:
        la, li = st_l.range(0, i)
        if la < INF and li != -1:
            edges.append((li, i, abs(i - li) * D + A[i] + A[li]))

        ra, ri = st_r.range(i, N)
        if ra < INF and ri != -1:
            edges.append((ri, i, abs(i - ri) * D + A[i] + A[ri]))

        st_l.update(i, (A[i] + (N - i) * D, i))
        st_r.update(i, (A[i] + i * D, i))

    # return [(i, j, abs(i - j) * D + A[i] + A[j])
    #         for i in range(N) for j in range(i + 1, N)]
    return edges


class SegmentTree:

    def __init__(self, size: int, op: Callable[[any, any], any], init: any = 0):
        """initialize SegmentTree
        :param size: Size of tree. This must be natural number.
        :param op: Operator which compares two numbers. This function return the
                representative value of two arguments.
        :param init: The initial value of element of tree.
        """
        if size < 1:
            raise Exception('size must be greater than 0 (actual = %d)' % size)

        self.__treesize = 1
        self.__init = init
        # tree size is the minimum number which is greater than or equal to
        # designed `size` and is power of 2.
        while self.__treesize < size:
            self.__treesize *= 2

        self.__size = self.__treesize
        self.__treesize = self.__treesize * 2 - 1

        self.__comp = op

        # initialize tree
        self.__tree = [init for _ in range(self.__treesize)]

    def range(self, l: int, r: int) -> int:
        """Returns the representative value in range [l, r)
        :param l: left value(include)
        :param r: right value(not include)
        :return: the representative value in range[l, r)
        """
        return self.__range(l, r, 0, 0, self.__size)

    def __range(self, l: int, r: int, k: int, kl: int, kr: int) -> int:
        """
        :param l: left value (include)
        :param r: right value (not include)
        :param k: node index
        :param kl: left value of node
        :param kr: right value of node
        """
        if kr <= l or r <= kl:
            # no crossing
            return self.__init
        if l <= kl and kr <= r:
            # including whole k's range
            return self.__tree[k]

        vl = self.__range(l, r, 2 * k + 1, kl, (kl + kr) // 2)
        vr = self.__range(l, r, 2 * k + 2, (kl + kr) // 2, kr)
        if vl is None:
            return vr
        if vr is None:
            return vl

        return self.__comp(vl, vr)

    def update(self, index: int, val: int):
        """update value at self.__tree[index]'s value
        """
        index += self.__size - 1
        self.__tree[index] = val

        while index > 0:
            index = (index - 1) // 2
            self.__tree[index] = self.__comp(
                self.__tree[2*index + 1], self.__tree[2*index + 2])

    def print(self):
        """for debug
        """
        print(self.__tree)


class UnionFindTree:

    def __init__(self, size: int):
        """UnionFindTreeを初期化します
        :param size: サイズ
        :return: UnionFindTree
        """
        if size < 0:
            raise Exception('size must be greater than 0.')

        self.__parent = [-1] * size

    def summarize(self, a: int, b: int):
        """aを含む木とbを含む木をまとめます
        :param a: 木a
        :param b: 木b
        """
        a = self.__root(a)
        b = self.__root(b)

        if a != b:
            self.__parent[b] = a

    def __root(self, a: int) -> int:
        """aの根を求めます
        :param a: 木の要素
        :return: 根
        """
        if self.__parent[a] == -1:
            return a
        else:
            return self.__root(self.__parent[a])

    def same(self, a: int, b: int) -> bool:
        """a と b が同じ木に属するかを判断します
        :param a: 木
        :param b: 木
        :return: a と b が同じ木なら True。そうでないなら False。
        """
        return self.__root(a) == self.__root(b)


if __name__ == "__main__":
    N, D = [int(s) for s in input().split()]
    A = [int(s) for s in input().split()]
    ans = connecting_cities(N, D, A)
    print(ans)

Submission status: Runtime Error

Solution code:
import itertools
from operator import itemgetter
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

def inpl(): return list(map(int, input().split()))
def cost(x, y):
    return D * abs(x - y) + A[x] + A[y]
N, D = inpl()
A = inpl()
minx = A.index(min(A))
Right = [(v - i*D, i) for i, v in enumerate(A)]
Left = [(v + i*D, i) for i, v in enumerate(A)][::-1]
Right = list(itertools.accumulate(Right[minx:], min))
Left = list(itertools.accumulate(Left[N - 1 - minx:], min))
hub = [0]
for _, i in itertools.chain(Left[::-1],Right,(0, N-1)):
    if hub[-1] != i:
        hub.append(i)
edge = [(cost(hub[i], k), hub[i], k) for i in range(len(hub)-1) for k in range(hub[i]+1, hub[i+1])]\
+ [(cost(hub[i+1], k), hub[i+1], k) for i in range(len(hub)-1) for k in range(hub[i], hub[i+1])]
edge.sort(reverse = True)
Uf = UnionFind(N)
ctr = 1
ans = 0
while ctr < N:
    v, i, j = edge.pop()
    if Uf.find(i) != Uf.find(j):
        Uf.union(i, j)
        ctr += 1
        ans += v
print(ans)

Submission status: Runtime Error

Solution code:
N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t

L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  t = Ll[cnt]
  L.append((A[i] + A[t] + (t - i) * D, i, t))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  t = Lr[cnt]
  L.append((A[i] + A[t] + (i - t) * D, t, i))

L = set(L)  
L.sort()

Submission status: Runtime Error

Solution code:
class Segmenttree_min():
    def __init__(self, number):
        n = 1
        inf = (1 << 31) - 1
        while n < number:
            n *= 2
        self.n = n
        self.list = [inf] * (2 * n - 1)

    def add(self, i, x):  # 0indexed ith add x
        i += self.n - 1
        self.list[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.list[i] = min(self.list[2 * i + 1], self.list[2 * i + 2])

    def search(self, a, b, k, l, r):  # call as search(a,b,0,0,self.n) minimun in [a,b)
        if r <= a or b <= l:
            return (1 << 31) - 1
        elif a <= l and r <= b:
            return self.list[k]
        else:
            vl = self.search(a, b, 2 * k + 1, l, (l + r) // 2)
            vr = self.search(a, b, 2 * k + 2, (l + r) // 2, r)
            return min(vl, vr)


class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  # 親を探す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  # x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)



N,D=map(int,input().split())
A=[int(i) for i in input().split()]
lefttree = Segmenttree_min(N)
dd={}
table=[]
for i in range(N):
    lefttree.add(i,A[i]+(N-1-i)*D)
    dd[A[i]+(N-1-i)*D]=i
    if i>0:
        s=lefttree.search(0,i,0,0,lefttree.n)
        y=dd[s]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
righttree = Segmenttree_min(N)
dr={}
for i in range(N-1,-1,-1):
    righttree.add(i,A[i]+i*D)
    dr[A[i]+i*D]=i
    if i<N-1:
        s=righttree.search(i+1,N,0,0,lefttree.n)
        y=dr[s]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
#print(table)
#print(dr)
table.sort()
uniontrees=Unionfindtree(N)
ans=0
for cost,s,t in table:
    if not uniontrees.connect(s,t):
        ans+=cost
        uniontrees.union(s,t)
print(ans)

Submission status: Runtime Error

Solution code:
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      T[xR][1] = T[yR][1] + 1
  return xR != yR

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


lf = 0
ri = N - 1

rt = (N-1) * D + A[N-1]
Ll = []
flg = False
if rt < (N-2) * D + A[N-2]:
  flg = True
  Ll.append((rt, N-1))
  
for i in range(N-2, 0, -1):
  if flg == False:
    if A[i] > A[i+1]:
      flg = True
      Ll.append((t, i + 1))
      ri = i + 1
  t = i * D + A[i]    
  if rt > t:
    if flg:
      Ll.append((t, i))
    rt = t
      
rt = (N-1) * D + A[0]
Lr = []
flg = False
if rt < (N-2) * D + A[1]:
  flg = True
  Lr.append((rt, 0))
for i in range(1, ri + 1):
  if flg == False:
    if A[i] > A[i-1]:
      flg = True
      Lr.append((t, i - 1))
      lf = i - 1
  t = (N - 1 - i) * D + A[i]
  if rt > t:
    if flg:
      Lr.append((t, i))
    rt = t
    
if flg == False:
  lf = ri
      
L = []

for i in range(0, lf):
  L.append((A[i] + A[lf] + (lf - i) * D, i, lf))
for i in range(N-1, ri, -1):
  L.append((A[i] + A[ri] + (i - ri) * D, ri, i))

if lf != ri:
  cnt = -1
  for i in range(lf, ri):
    if i >= Ll[cnt][1]:
      cnt -= 1
    L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

  cnt = -1
  for i in range(ri , lf, -1):
    if i <= Lr[cnt][1]:
      cnt -= 1
    L.append((A[i] + Lr[cnt][0] - (N - 1 - i) * D, Lr[cnt][1], i))

L = list(set(L))
L.sort()

T = [[i, 0] for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Runtime Error

Solution code:
def getR(x):
  if T[x][0] == x:
    return x
  return getR(T[x][0])
 
def judT(x, y):
  xR = getR(x)
  yR = getR(y)
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[yR][0] = xR
      T[xR][1] = T[yR][1] + 1
    else:
      T[xR][0] = yR
      T[yR][1] = T[xR][1] + 1
  return xR != yR

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

rt = (N-1) * D + A[N-1]
Ll = [(rt, N-1)]
for i in range(N-2, 0, -1):
  t = i * D + A[i]
  if rt > t:
    Ll.append((t, i))
    rt = t

rt = (N-1) * D + A[0]
Lr = [(rt, 0)]
for i in range(1, N-1):
  t = (N - 1 - i) * D + A[i]
  if rt > t:
    Lr.append((t, i))
    rt = t
    
L = []
cnt = -1
for i in range(N - 1):
  if i >= Ll[cnt][1]:
    cnt -= 1
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt][1]:
    cnt -= 1
  L.append((A[i] + Lr[cnt][0] - (N - 1 - i) * D, Lr[cnt][1], i))

L = list(set(L))
L.sort()

#print(L)

T = [[i, 0] for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Runtime Error

Solution code:
def getR(x):
  if T[x] == x:
    return x
  return getR(T[x])
 
def judT(x, y):
  xR = getR(x)
  yR = getR(y)
  if xR != yR:
    T[xR] = yR
  return xR != yR

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

rt = (N-1) * D + A[N-1]
Ll = [(rt, N-1)]
for i in range(N-2, 0, -1):
  t = i * D + A[i]
  if rt > t:
    Ll.append((t, i))
    rt = t

rt = (N-1) * D + A[0]
Lr = [(rt, 0)]
for i in range(1, N-1):
  t = (N - 1 - i) * D + A[i]
  if rt > t:
    Lr.append((t, i))
    rt = t
    
L = []
cnt = -1
for i in range(N - 1):
  if i >= Ll[cnt][1]:
    cnt -= 1
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt][1]:
    cnt -= 1
  L.append((A[i] + Lr[cnt][0] - (N - 1 - i) * D, Lr[cnt][1], i))

L.sort()

#print(L)

T = [i for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Runtime Error

Solution code:
def getR(x):
  if T[x] == x:
    return x
  return getR(T[x])
 
def judT(x, y):
  xR = getR(x)
  yR = getR(y)
  if xR != yR:
    T[xR] = yR
  return xR != yR

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

rt = (N-1) * D + A[N-1]
Ll = [(rt, N-1)]
for i in range(N-2, 0, -1):
  t = i * D + A[i]
  if rt > t:
    Ll.append((t, i))
    rt = t
Ll.reverse()

rt = (N-1) * D + A[0]
Lr = [(rt, 0)]
for i in range(1, N-1):
  t = (N - 1 - i) * D + A[i]
  if rt > t:
    Lr.append((t, i))
    rt = t
Lr.reverse()
    
L = []
cnt = 0
for i in range(N - 1):
  if i >= Ll[cnt][1]:
    cnt += 1
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = 0
for i in range(N-1, 0, -1):
  if i <= Lr[cnt][1]:
    cnt += 1
  L.append((A[i] + Lr[cnt][0] - (N - 1 - i) * D, Lr[cnt][1], i))

L = list(set(L))
L.sort()

#print(L)

T = [i for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Runtime Error

Solution code:
def getR(x):
  if T[x] == x:
    return x
  return getR(T[x])
 
def judT(x, y):
  xR = getR(x)
  yR = getR(y)
  if xR != yR:
    T[xR] = yR
  return xR != yR

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

Ll = [(A[i] + i * D, i) for i in range(1, N)]
Lr= [(A[i] + (N-i-1) * D, i) for i in range(0, N-1)]
Ll.sort()
Lr.sort()

L = []
LC = 0
cnt = 0
while True:
  while Ll[cnt][1] > LC:
    L.append((A[LC] + Ll[cnt][0] - LC * D, LC, Ll[cnt][1]))
    LC += 1
  if LC == N-1:
    break
  while Ll[cnt][1] <= LC:
    cnt += 1

cnt = 0
RC = N-1
while True:
  while Lr[cnt][1] < RC:
    L.append((A[RC] + Lr[cnt][0] - (N - 1 - RC) * D, Lr[cnt][1], RC))
    RC -= 1
  if RC == 0:
    break
  while Lr[cnt][1] >= RC:
    cnt += 1

L = list(set(L))
L.sort()

T = [i for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Runtime Error

Solution code:
readline = open(0).readline
write = open(1, 'w').write

N, D = map(int, readline().split())
*A, = map(int, readline().split())

N0 = 2**(N-1).bit_length()
INF = (10**18, -1)
ldata = [INF]*(2*N0+1)
rdata = [INF]*(2*N0+1)

P = []; Q = []
for x in range(N0+1):
    y = N0 + x
    z = (y // (y & -y)) >> 1
    P.append(2*z-1 if z else 0)
    z = (y // (y & -y))
    Q.append(z-1)
Q.reverse()

def update(data, k, x):
    k += N0-1
    data[k] = x
    while k:
        k = (k - 1) >> 1
        data[k] = min(data[2*k+1], data[2*k+2])

# lquery: query [0, r)
def lquery(r):
    yield -1
    while r:
        yield P[r]
        r -= r & -r

# rquery: query [l, N0)
def rquery(l):
    yield -1
    r = N0 - l
    while r:
        yield Q[r]
        r -= r & -r


*I, = range(N)
I.sort(key=A.__getitem__)

lget = ldata.__getitem__
rget = rdata.__getitem__
E = []
for i in I:
    c, k = min(map(lget, lquery(i)))
    if k != -1:
        c -= (N-1-i)*D
        E.append((c + A[i], k, i))
    c, k = min(map(rget, rquery(i+1)))
    if k != -1:
        c -= i*D
        E.append((c + A[i], i, k))
    update(ldata, i, ((N-1-i)*D + A[i], i))
    update(rdata, i, (i*D + A[i], i))

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1


E.sort()
ans = 0
for c, i, j in E:
    if unite(i, j):
        ans += c
write("%d\n" % ans)

Submission status: Runtime Error

Solution code:
N, D = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N-1).bit_length()
INF = (10**18, -1)
ldata = [INF]*(2*N0)
rdata = [INF]*(2*N0)

P = []; Q = []
for x in range(N0+1):
    y = N0 + x
    z = (y // (y & -y)) >> 1
    P.append(2*z-1 if z else 0)
    z = (y // (y & -y))
    Q.append(z-1)
Q.reverse()

def update(data, k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) >> 1
        data[k] = min(data[2*k+1], data[2*k+2])

# lquery: query [0, r)
def lquery(data, r):
    s = INF
    while r:
        v = P[r]
        s = min(s, data[P[r]])
        r -= (r & -r)
    return s

# rquery: query [l, N0)
def rquery(data, l):
    s = INF
    r = N0 - l
    while r:
        s = min(s, data[Q[r]])
        r -= (r & -r)
    return s

*I, = range(N)
I.sort(key=A.__getitem__)

E = []
for i in I:
    c, k = lquery(ldata, i)
    if k != -1:
        c -= (N-1-i)*D
        E.append((c + A[i], k, i))
    c, k = rquery(rdata, i+1)
    if k != -1:
        c -= i*D
        E.append((c + A[i], i, k))
    update(ldata, i, ((N-1-i)*D + A[i], i))
    update(rdata, i, (i*D + A[i], i))

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1


E.sort()
ans = 0
for c, i, j in E:
    if unite(i, j):
        ans += c
print(ans)

Submission status: Runtime Error

Solution code:
N, D = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N-1).bit_length()
INF = (10**18, -1)
ldata = [INF]*(2*N0)
rdata = [INF]*(2*N0)

def update(data, k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
def query(data, l, r):
    if l >= r:
        return INF
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

*I, = range(N)
I.sort(key=A.__getitem__)

E = []
for i in I:
    c, k = query(ldata, 0, i)
    if k != -1:
        c -= (N-1-i)*D
        E.append((c + A[i], k, i))
    c, k = query(rdata, i+1, N)
    if k != -1:
        c -= i*D
        E.append((c + A[i], i, k))
    update(ldata, i, ((N-1-i)*D + A[i], i))
    update(rdata, i, (i*D + A[i], i))

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1


E.sort()
ans = 0
for c, i, j in E:
    if unite(i, j):
        ans += c
print(ans)

Submission status: Runtime Error

Solution code:
N, D = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N-1).bit_length()
INF = (10**18, -1)
ldata = [INF]*(2*N0)
rdata = [INF]*(2*N0)

for i in range(N0-2, -1, -1):
    ldata[i] = min(ldata[2*i+1], ldata[2*i+2])
    rdata[i] = min(rdata[2*i+1], rdata[2*i+2])
def update(data, k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
def query(data, l, r):
    if l >= r:
        return INF
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

*I, = range(N)
I.sort(key=A.__getitem__)

E = []
for i in I:
    c, k = query(ldata, 0, i)
    if k != -1:
        c -= (N-1-i)*D
        E.append((c + A[i], k, i))
    c, k = query(rdata, i+1, N)
    if k != -1:
        c -= i*D
        E.append((c + A[i], i, k))
    update(ldata, i, ((N-1-i)*D + A[i], i))
    update(rdata, i, (i*D + A[i], i))

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1


E.sort()
ans = 0
for c, i, j in E:
    if unite(i, j):
        ans += c
print(ans)