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: Time Limit Exceeded

Solution code:
# パラメータ入力
N, D = map(int,input().split())
A = list(map(int,input().split()))

# 各都市間のコストを求める
def cost(A, i, j):
    return (abs(i-j) * D) + A[i - 1] + A[j - 1]

cost_list = []
a_sum = len(A)
i = a_sum
j = 1
while i > 0:
    while j < i:
        cost_list.append([cost(A, i, j), i, j])
        j += 1
    j = 1
    i -= 1

# 各都市間のコストを低い順にソートする
cost_list.sort()

# 小さい順からN-1個の分の総和を求める
# その際最低1つ以上の新規国を繋ぐ必要がある
connectd_country = {}
min_cost_sum = 0
count = 0
unused_road_list = []
used_road_list = []

# 同じ国リスト間をループする場合は、カウントしない
# 繋いだ国があれば、その国クリストに繋ぐ
# 繋いだ国がなければ、新規に国リストを作る
# 国リスト間を跨ぐ場合は、国リストをマージする
group_map = {}
currnt_group_index = 1
def add_group(country_num_1, country_num_2):
    if (country_num_1 in group_map) == False and (country_num_2 in group_map) == False:
        global currnt_group_index
        group_map[country_num_1] = currnt_group_index
        group_map[country_num_2] = currnt_group_index
        currnt_group_index += 1
    elif (country_num_1 in group_map) == True and (country_num_2 in group_map) == False:
        group_map[country_num_2] = group_map[country_num_1]
    elif (country_num_1 in group_map) == False and (country_num_2 in group_map) == True:
        group_map[country_num_1] = group_map[country_num_2]
    else:
        if group_map[country_num_1] != group_map[country_num_2]:
            for key in group_map:
                if group_map[key] == group_map[country_num_2]:
                    group_map[key] = group_map[country_num_1]

def can_construct(country_num_1, country_num_2):
    if (country_num_1 in group_map) == False:
        return True
    if (country_num_2 in group_map) == False:
        return True
    if group_map[country_num_1] != group_map[country_num_2]:
        return True
    return False

for road in cost_list:
    contry_1 = road[1]
    contry_2 = road[2]
    if can_construct(contry_1, contry_2) == False:
        continue
    add_group(contry_1, contry_2)
    min_cost_sum += road[0]
    used_road_list.append(road)
    count += 1
    if count == a_sum - 1:
        break

print(min_cost_sum)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:

    def __init__(self, n, sentinel=0):
        n2 = 1 << (n - 1).bit_length()
        self.n = n2
        self.data = [sentinel] * ((n2 << 1) - 1)
        self.offset = n2 - 1

    def update(self, k, x):
        i = k + self.offset
        self.data[i] = x
        while i:
            p = (i - 1) // 2
            if self.data[p] > self.data[i]:
                self.data[p] = self.data[i]
            else:
                break
            i = p

    def get_left_min(self, k):
        i = k + self.offset - 1
        ret = self.data[i]
        while i:
            if i % 2 == 0:
                ret = min(ret, self.data[i - 1])
            i = (i - 1) // 2
        return ret

    def get_right_min(self, k):
        i = k + self.offset + 1
        ret = self.data[i]
        while i:
            if i % 2 == 1:
                ret = min(ret, self.data[i + 1])
            i = (i - 1) // 2
        return ret


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

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

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n, d = map(int, input().split())
aaa = list(map(int, input().split()))
seg_l = SegmentTree(n, (10 ** 10, -1))
seg_r = SegmentTree(n, (10 ** 10, -1))
bbb = sorted((a, i) for i, a in enumerate(aaa))
edges = set()

for a, i in bbb:
    cost_l = -i * d + a
    cost_r = i * d + a
    seg_l.update(i, (cost_l, i))
    seg_r.update(i, (cost_r, i))

    di = i * d
    if i > 0:
        base_cost, j = seg_l.get_left_min(i)
        if j > -1:
            edges.add((base_cost + di + a, j, i))
    if i < n - 1:
        base_cost, j = seg_r.get_right_min(i)
        if j > -1:
            edges.add((base_cost - di + a, i, j))

uft = UnionFind(n)
ans = 0
for c, i, j in sorted(edges):
    if uft.find(i, j):
        continue
    ans += c
    uft.union(i, j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    SENTINEL = (float('inf'), 0)

    def __init__(self, n):
        n2 = 1 << (n - 1).bit_length()
        self.n = n2
        self.data = [self.SENTINEL] * ((n2 << 1) - 1)
        self.offset = n2 - 1

    def create(self, aaa):
        s = self.offset
        t = s + len(aaa)
        self.data[s:t] = aaa
        for i in range(self.offset - 1, -1, -1):
            self.data[i] = min(self.data[i * 2 + 1], self.data[i * 2 + 2])

    def get_left_min(self, k):
        i = k + self.offset - 1
        ret = self.data[i]
        while i:
            if i % 2 == 0:
                ret = min(ret, self.data[i - 1])
            i = (i - 1) // 2
        return ret

    def get_right_min(self, k):
        i = k + self.offset + 1
        ret = self.data[i]
        while i:
            if i % 2 == 1:
                ret = min(ret, self.data[i + 1])
            i = (i - 1) // 2
        return ret


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

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

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n, d = map(int, input().split())
aaa = list(map(int, input().split()))
seg_l = SegmentTree(n)
seg_r = SegmentTree(n)
costs_l = [((i - n + 1) * d + a, n - i - 1) for i, a in enumerate(reversed(aaa))]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]
costs_l.reverse()
seg_l.create(costs_l)
seg_r.create(costs_r)

edges = set()
nd = (n - 1) * d
for i, a in enumerate(aaa):
    di = i * d

    if i > 0:
        base_cost, j = seg_l.get_left_min(i)
        edges.add((base_cost + di + a, j, i))
    if i < n - 1:
        base_cost, j = seg_r.get_right_min(i)
        edges.add((base_cost - di + a, i, j))

uft = UnionFind(n)
ans = 0
for c, i, j in sorted(edges):
    if uft.find(i, j):
        continue
    ans += c
    uft.union(i, j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d = map(int,input().split())
a = list(map(int,input().split()))
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
 
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        else:
          return False
        return True
      
UF = UnionFind(n)
ki = n
ans = 0
inf = float("inf")
while ki >= 2:
  L =[]
  R = []
  hen = [[-1,-1,inf] for i in range(n)]
  for i in range(n):
    r = UF.find(i)
    for j,k in L:
      if k != r:
        if hen[r][2] > j+i*d+a[i]:
          hen[r] = [r,k,j+i*d+a[i]]
    L.append([-i*d+a[i],r])
  for i in range(n-1,-1,-1):
    r = UF.find(i)
    for j,k in R:
      if k != r:
        if hen[r][2] > j-i*d+a[i]:
          hen[r] = [r,k,j-i*d+a[i]]
    R.append([i*d+a[i],r])
  for i,j,k in hen:
    if k == float("inf"):
      continue
    if UF.union(i,j):
        ans += k
        ki -=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
#sys.setrecursionlimit(200000)
input = sys.stdin.readline
#n = int(input())
n,d = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
kore = []
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
 
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        else:
          return False
        return True

N0 = 2**(n).bit_length()
INF = (2**31-1)
data = [[INF]*2 for i in range(2*N0)]
data2 = [[INF]*2 for i in range(2*N0)]
def update(k, x,y):
    k += N0-1
    data[k] = [x,y]
    while k >= 0:
        k = (k - 1) // 2
        if data[2*k+1][0] > data[2*k+2][0]:
            data[k] =  data[2*k+2]
        else:
            data[k] =  data[2*k+1]
def query(l, r):
    L = l + N0; R = r + N0
    s = [INF,INF]
    while L < R:
        if R & 1:
            R -= 1
            if s[0] > data[R-1][0]:
                s = data[R-1]
 
        if L & 1:
            if s[0] > data[L-1][0]:
                s = data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s
def update2(k, x,y):
    k += N0-1
    data2[k] = [x,y]
    while k >= 0:
        k = (k - 1) // 2
        if data2[2*k+1][0] > data2[2*k+2][0]:
            data2[k] =  data2[2*k+2]
        else:
            data2[k] =  data2[2*k+1]
def query2(l, r):
    L = l + N0; R = r + N0
    s = [INF,INF]
    while L < R:
        if R & 1:
            R -= 1
            if s[0] > data2[R-1][0]:
                s = data2[R-1]
 
        if L & 1:
            if s[0] > data2[L-1][0]:
                s = data2[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s
b = []
for i in range(n):
    b.append([a[i],i])
b.sort()
kimeta = UnionFind(n)
for i in range(n):
    c = b[i]
    hidari = query(0,c[1])
    migi = query2(c[1],n)
    if hidari[1] != INF:
        kore.append([a[hidari[1]]+c[0]+d*abs(c[1]-hidari[1]),c[1],hidari[1]])
    if migi[1] != INF:
        kore.append([a[migi[1]]+c[0]+d*abs(migi[1]-c[1]),c[1],migi[1]])
    update(c[1],c[0]+d*(n-c[1]),c[1])
    update2(c[1],c[0]+d*c[1],c[1])    
kore.sort()
for i,j,k in kore:
    if kimeta.union(j,k):
        ans += i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def kruskal(v_count: int, edges: list) -> int:
    """
    :param v_count: 頂点数
    :param edges: [(weight, from, to), ... ]
    """
    from itertools import islice
    tree = [-1]*v_count

    def get_root(x) -> int:
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(a) -> bool:
        x, y = get_root(a[1]), get_root(a[2])
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for w, _s, _t in islice(filter(unite, sorted(edges)), v_count-1):
        cost += w
    return cost


class BIT():
    def __init__(self, number):
        self.n = number
        self.list = [10 ** 22] * (number + 1)

    def add(self, i, x):  # ith added x  1indexed
        while i <= self.n:
            self.list[i] = min(x, self.list[i])
            i += i & -i

    def search(self, i):  # 1-i min
        s = 10 ** 22
        while i > 0:
            s = min(s, self.list[i])
            i -= i & -i
        return s

import time
import random
start = time.clock()
      
N,D=2*10**5, random.randint(1,10**9)
A=[]
for _ in range(N):
    A.append(random.randint(1,10**9))
B=[(A[i],i) for i in range(N)]
B.sort()
table=[]
lbit=BIT(N)
rbit=BIT(N)
dl={}
dr={}

print("defined variables: {} sec".format(time.clock()-start))

for b,i in B:
    lbit.add(i+1,b+(N-1-i)*D)
    rbit.add(N-i,b+i*D)
    dl[b+(N-1-i)*D]=i
    dr[b+i*D]=i
    sl=lbit.search(i)
    sr=rbit.search(N-i-1)
    if sl<=10**21:
        y=dl[sl]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
    if sr<=10**21:
        y=dr[sr]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))

print("collected edges: {} sec".format(time.clock()-start))

print(kruskal(N, table))

print("calculated minimum cost: {} sec".format(time.clock()-start))

Submission status: Time Limit Exceeded

Solution code:
# import time
# start = time.clock()

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())

# RMQ (セグメント木)
class SegmentTree:
    def __init__(self, n, func, default):
        self.n = pow(2, (n-1).bit_length())
        self.func = func
        self.default = default
        
        self.segtree = [default for _ in range(2*self.n-1)]
        
    def update(self, idx, value):
        idx += (self.n-1)
        self.segtree[idx] = value
        while idx > 0:
            idx = (idx-1) // 2
            self.segtree[idx] = self.func(self.segtree[2*idx+1],
                                          self.segtree[2*idx+2])
            
    def query(self, a, b, idx, l, r):
        if r <= a or b <= l:
            return self.default
        
        elif a <= l and r <= b:
            return self.segtree[idx]

        else:
            return self.func(self.query(a,b,2*idx+1,l,(l+r)//2),
                             self.query(a,b,2*idx+2,(l+r)//2,r))
    
    def between(self, a, b):
        return self.query(a,b,0,0,self.n)
    
    
    def reset(self):
        self.segtree = [self.default]*(2*self.n-1)
        
        
    def inarray(self, arr):
        for i, ai in enumerate(arr):
            idx = i + (self.n-1)
            self.update(idx, ai)
    
# クラスカル法
class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    
# edgesは(cost, prev_node, nex_node)をE本格納しているリスト
def kruskal(edges: list, node_num: int) -> int:
    edges.sort(key=lambda x:x[0])
    
    uf = UnionFind(node_num)
    rem = node_num-1
    ans = 0
    for cost, prev, nex in edges:
        if uf.find(prev) != uf.find(nex):           
            uf.unite(prev, nex)
            ans += cost
            rem -= 1
            
        if rem == 0:
            break
        
    return ans

# セグメント木の判定関数
def segfunc(a:list, b:list):
    if a[0] > b[0]:
        return b
    else:
        return a
    

# 入力
n,d = li()
a = list(li())

INFP = [float("inf"), -1]


# 都市番号ラベリング, 規模順にソート
scale_idx = [(ai, i) for i,ai in enumerate(a)]
scale_idx.sort()


# 左を見るセグメント木
segleft = SegmentTree(n, segfunc, INFP)

# 右を見るセグメント木
segright = SegmentTree(n, segfunc, INFP)


edges = []

# print("defined variables: {}sec".format(time.clock()-start))

# 規模順に実行
for scale, idx in scale_idx:
    
    # 左側最小を取得
    scj, idxj = segleft.between(0, idx)
    if [scj, idxj] != INFP:
        cost = scj + idx*d + scale
        edges.append([cost, idx, idxj])
    
    # 右側最小を取得
    scj, idxj = segright.between(idx+1, n)
    if [scj, idxj] != INFP:
        cost = scj - idx*d + scale
        edges.append([cost, idx, idxj])
    
    # セグメント木アップデート
    segleft.update(idx, [scale - idx*d, idx])
    segright.update(idx, [scale + idx*d, idx])
    

# print("collected edges: {}sec".format(time.clock()-start))    

# 集めた辺でクラスカル法
ans = kruskal(edges, n)

# print("calculated minimum cost: {}sec".format(time.clock()-start))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop,heappush

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()]
dd={}
table=[]
sta=10**22
for i in range(N):
    if i>0:
        y=dd[sta]
        heappush(table,(A[i]+A[y]+D*abs(i-y),i,y))
    sta=min(sta,A[i]+(N-1-i)*D)
    dd[A[i]+(N-1-i)*D]=i
#print(table)
#righttree = BIT(N)
dr={}
sta=10**22
for i in range(N-1,-1,-1):
    if i<N-1:
        #print(i, dr,s)
        y=dr[sta]
        heappush(table,(A[i]+A[y]+D*abs(i-y),i,y))
    sta=min(sta,A[i]+i*D)
    dr[A[i]+i*D]=i
uniontrees=Unionfindtree(N)
#print(len(table))
#print(table)
ans=0
while table:
    cost,s,t=heappop(table)
    if not uniontrees.connect(s,t):
        ans+=cost
        uniontrees.union(s,t)
print(ans)
"""
#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: Time Limit Exceeded

Solution code:
def main():
  N, D = tuple(map(int,input().split()))
  A = tuple(map(int, input().split()))

  rt = A[N - 1]
  Ll = [N - 1]
  k = N - 1
  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 = 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
  Lr.append(N-1)

  Ll = tuple(Ll)
  Lr = tuple(Lr)

  L = []
  lC = -1
  rC = 1
  lCmax = -len(Ll) - 1
  for i in range(N-1):
    if i >= Ll[lC]:
      lC -= 1
    for j in range(lC, lCmax, -1):
      t = Ll[j]
      if A[i] >= A[t]: 
        L.append((A[i] + A[t] + (t - i) * D, i, t))
        break
    k = i + 1
    if k > Lr[rC]:
      rC += 1
    for j in range(rC - 1, -1, -1):
      t = Lr[j]
      if A[k] > A[t]:
        L.append((A[k] + A[t] + (k - t) * D, t, k))
        break
  L.sort()

  T = [i for i in range(N)]
  C = 0
  A = 0
  for i in L:
    xR = i[1]
    xC = 0
    yR = i[2]
    yC = 0
    while T[xR] != xR:
      xC += 1
      xR = T[xR]
    while T[yR] != yR:
      yC += 1
      yR = T[yR]
    if xR != yR:
      if xC < yC:
        T[xR] = yR
      else:
        T[yR] = xR
    if xR != yR:
      C += 1
      A += i[0]
      #print(i)
      if C == N-1:
        break
   
  print(A)
  
main()

Submission status: Time Limit Exceeded

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

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

rt = A[N - 1]
Ll = [N - 1]
k = N - 1
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 = 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
Lr.append(N-1)

Ll = tuple(Ll)
Lr = tuple(Lr)

L = []
lC = -1
rC = 1
lCmax = -len(Ll) - 1
for i in range(N-1):
  if i >= Ll[lC]:
    lC -= 1
  for j in range(lC, lCmax, -1):
    t = Ll[j]
    if A[i] >= A[t]: 
      L.append((A[i] + A[t] + (t - i) * D, i, t))
      break
  k = i + 1
  if k > Lr[rC]:
    rC += 1
  for j in range(rC - 1, -1, -1):
    t = Lr[j]
    if A[k] > A[t]:
      L.append((A[k] + A[t] + (k - t) * D, t, k))
      break
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: Time Limit Exceeded

Solution code:
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    T[T[xR][0]][1] = T[xR][1] + 1
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    T[T[yR][0]][1] = T[yR][1] + 1
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      if T[yR][1] < T[xR][1] + 1:
        T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      if T[xR][1] < T[yR][1] + 1:
        T[xR][1] = T[yR][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 = [N-1]
k = N - 2
for i in range(N-2, 0, -1):
  t = (i - k) * D + A[i]
  if rt > t:
    Ll.append(i)
    k = i
    rt = A[i]
    
rt = (N-1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N-1):
  t = (k - i) * D + A[i]
  if rt > t:
    Lr.append(i)
    k = i
    rt = A[i]

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

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

#print(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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter
n,d = map(int, input().split())
al = list(map(int, input().split()))
edge = []

def rec(left, right):
    if right-left<=1:
        return

    mid = (left+right)//2

    leftmin = left
    for i in range(left,mid):
        t = al[i] - d*i
        t2 = al[leftmin] - d*leftmin
        if t<t2:
            leftmin = i

    rightmin = mid
    for i in range(mid,right):
        t = al[i] + d*i
        t2 = al[rightmin] + d*rightmin
        if t<t2:
            rightmin = i

    for i in range(left,mid):
        edge.append((al[rightmin]+al[i]+abs(rightmin-i)*d, (i,rightmin)))
    for i in range(mid,right):
        edge.append((al[i]+al[leftmin]+abs(i-leftmin)*d, (leftmin,i)))

    rec(left,mid)
    rec(mid,right)

rec(0,n)

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return

        if x<y:
            self.par[y] = x
        else:
            self.par[x] = y

    def same(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(n)
edge.sort(key=itemgetter(0))
res = 0
for e in edge:
    w = e[0]
    v,u = e[1]

    if uf.same(u,v):
        continue
    res += w
    uf.unite(v,u)

print(res)

Submission status: Time Limit Exceeded

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

# RMQ (セグメント木)
class SegmentTree:
    def __init__(self, n, func, default):
        self.n = pow(2, (n-1).bit_length())
        self.func = func
        self.default = default
        
        self.segtree = [default for _ in range(2*self.n-1)]
        
    def update(self, idx, value):
        idx += (self.n-1)
        self.segtree[idx] = value
        while idx > 0:
            idx = (idx-1) // 2
            self.segtree[idx] = self.func(self.segtree[2*idx+1],
                                          self.segtree[2*idx+2])
            
    def query(self, a, b, idx, l, r):
        if r <= a or b <= l:
            return self.default
        
        elif a <= l and r <= b:
            return self.segtree[idx]

        else:
            return self.func(self.query(a,b,2*idx+1,l,(l+r)//2),
                             self.query(a,b,2*idx+2,(l+r)//2,r))
    
    def between(self, a, b):
        return self.query(a,b,0,0,self.n)
    
    
    def reset(self):
        self.segtree = [self.default]*(2*self.n-1)
        
        
    def inarray(self, arr):
        for i, ai in enumerate(arr):
            idx = i + (self.n-1)
            self.update(idx, ai)
    
# クラスカル法
class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    
# edgesは(cost, prev_node, nex_node)をE本格納しているリスト
def kruskal(edges: list, node_num: int) -> int:
    edges.sort(key=lambda x:x[0])
    
    uf = UnionFind(node_num)
    rem = node_num-1
    ans = 0
    for cost, prev, nex in edges:
        if uf.find(prev) != uf.find(nex):           
            uf.unite(prev, nex)
            ans += cost
            rem -= 1
            
        if rem == 0:
            break
        
    return ans

# セグメント木の判定関数
def segfunc(a:list, b:list):
    if a[0] > b[0]:
        return b
    else:
        return a
    

# 入力
n,d = li()
a = list(li())

INFP = [float("inf"), -1]


# 都市番号ラベリング, 規模順にソート
scale_idx = [(ai, i) for i,ai in enumerate(a)]
scale_idx.sort()


# 左を見るセグメント木
segleft = SegmentTree(n, segfunc, INFP)

# 右を見るセグメント木
segright = SegmentTree(n, segfunc, INFP)


edges = []

# 規模順に実行
for scale, idx in scale_idx:
    
    # 左側最小を取得
    scj, idxj = segleft.between(0, idx)
    if [scj, idxj] != INFP:
        cost = scj + idx*d + scale
        edges.append([cost, idx, idxj])
    
    # 右側最小を取得
    scj, idxj = segright.between(idx+1, n)
    if [scj, idxj] != INFP:
        cost = scj - idx*d + scale
        edges.append([cost, idx, idxj])
    
    # セグメント木アップデート
    segleft.update(idx, [scale - idx*d, idx])
    segright.update(idx, [scale + idx*d, idx])
    

    

# 集めた辺でクラスカル法
ans = kruskal(edges, n)
print(ans)

Submission status: Time Limit Exceeded

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()))

L = [((j-i) * D + A[i] + A[j], i, j) for i in range(N) for j in range(i+1, N)]
 
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)