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: Wrong Answer

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

    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(
            yield (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(
            yield (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 edges


class SegmentTree:

    # def __init__(self, size: int, op: Callable[[any, any], any], init: any = 0):
    def __init__(self, size, op, init):
        """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: Wrong Answer

Solution code:
import itertools
def inpl(): return list(map(int, input().split()))
def cost(x, y):
    if y == -1:
        return float('inf')
    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 = [-1]
for _, i in itertools.chain(Left[::-1],Right):
    if hub[-1] != i:
        hub.append(i)
hub.append(-1)
ctr = 1
ans = sum([cost(i, j) for i, j in zip(hub[1:-1], hub[2:-1])])
for i in range(N):
    if hub[ctr] == i:
        ctr += 1
    else:
        ans += min(cost(i, hub[ctr-1]), cost(i, hub[ctr]))
print(ans)

Submission status: Wrong Answer

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):
    if hub[-1] != i:
        hub.append(i)
hub.append(N-1)
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: Wrong Answer

Solution code:
import heapq
import itertools
from operator import itemgetter
from collections import defaultdict
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 = itertools.accumulate(Right[minx:], min)
Left = itertools.accumulate(Left[N - 1 - minx:], min)
hub = set(map(itemgetter(1), Right))
hub.update(map(itemgetter(1), Left))
hub.add(0)
hub.add(N-1)
hub = list(sorted(hub))
edge = [(cost(hub[i], k), hub[i], k) for i in range(len(hub)-1) for k in range(hub[i], 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
print(edge)
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: Wrong Answer

Solution code:
import itertools
def an(n,d,a):
    kumi=list(itertools.combinations(range(0,n), 2))
    cost=[0]*len(kumi)
    z=0
    
  
    for i,j in kumi:
        cost[z]=((abs(i-j)*d+a[i]+a[j]),(i,j))
        z+=1
    
    cost.sort()

    ans=0

    ki=[]
    for i in range(len(cost)):
        hen1=cost[i][1][0]
        hen2=cost[i][1][1]

        if hen1 in ki and hen2 in ki:
            pass
        else:

            ans+=cost[i][0]

        ki.append(hen1)
        ki.append(hen2)
        ki=list(set(ki))
        if len(ki)==n:
            break


    return ans


n,d=map(int,input().split())
print(an(n,d,[int(i) for i in input().split()]))

Submission status: Wrong Answer

Solution code:
import itertools
def an(n,d,a):
    kumi=list(itertools.combinations(range(0,n), 2))
    cost=[0]*len(kumi)
    z=0
    for i,j in kumi:
        cost[z]=((abs(i-j)*d+a[i]+a[j]),(i,j))
        z+=1
    cost.sort()

    ans=0

    ki=[]
    for i in range(len(cost)):
        hen1=cost[i][1][0]
        hen2=cost[i][1][1]

        if not hen1 in ki or not hen2 in ki:
            ans+=cost[i][0]
        ki.append(hen1)
        ki.append(hen2)
        ki=list(set(ki))
        if len(ki)==n:
            break


    return ans


n,d=map(int,input().split())
print(an(n,d,[int(i) for i in input().split()]))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


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()))
costs_l = [(-i * d + a, i) for i, a in enumerate(aaa)]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]

prev = (float('inf'),)
for i in range(n):
    prev = costs_l[i] = min(prev, costs_l[i])
prev = (float('inf'),)
for i in range(n - 1, -1, -1):
    prev = costs_r[i] = min(prev, costs_r[i])

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

    if i > 0:
        base_cost, j = costs_l[i - 1]
        edges.add((base_cost + di + a, j, i))
    if i < n - 1:
        base_cost, j = costs_r[i + 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: Wrong Answer

Solution code:
from itertools import accumulate


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()))
costs_l = [(-i * d + a, i) for i, a in enumerate(aaa)]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]
costs_l_acc = list(accumulate(costs_l, min))
costs_r_acc = list(accumulate(reversed(costs_r), min))
costs_r_acc.reverse()

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

    if i > 0:
        base_cost, j = costs_l_acc[i - 1]
        edges.add((base_cost + di + a, j, i))
    if i < n - 1:
        base_cost, j = costs_r_acc[i + 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: Wrong Answer

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()
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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
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




N,D=map(int,input().split())
A = [int(i) for i in input().split()]
#print("defined variables: {} sec".format(time.clock() - start))
dd={}
table=[]
sta=10**22
for i in range(N):
    if i>0:
        y=dd[sta]
        table.append((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]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
    sta=min(sta,A[i]+i*D)
    dr[A[i]+i*D]=i
#print("collected edges: {} sec".format(time.clock() - start))
#print(len(table))
#print(table)
print(kruskal(N,table))
#print("calculated minimum cost: {} sec".format(time.clock() - start))

Submission status: Wrong Answer

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


N,D=map(int,input().split())
A=[int(i) for i in input().split()]
B=[(A[i],i) for i in range(N)]
B.sort()
table=[]
lbit=BIT(N)
rbit=BIT(N)
dl={}
dr={}
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(table)
print(kruskal(N, table))

Submission status: Wrong Answer

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


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]
        table.append((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
dr={}
sta=10**22
for i in range(N-1,-1,-1):
    if i<N-1:
        y=dr[sta]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
    sta=min(sta,A[i]+i*D)
    dr[A[i]+i*D]=i
print(kruskal(N, table))

Submission status: Wrong Answer

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

import sys
from operator import itemgetter

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]
        table.append((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]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
    sta=min(sta,A[i]+i*D)
    dr[A[i]+i*D]=i
print(kruskal(N, table))

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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

  A2 = [[A[i], i, 0] for i in range(N)]
  A2.sort()
  for i in range(N):
    A2[i][2] = i
  A2.sort(key = lambda x: x[1])
  A2 = tuple(A2)
  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

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

  L = []
  lC = -1
  rC = -1
  for i in range(N-1):
    if i >= Ll[lC]:
      lC -= 1
    t = Ll[lC]
    if A2[i][2] > A2[t][2]: 
      L.append((A[i] + A[t] + (t - i) * D, i, t))
    k = N - 1 - i
    if k <= Lr[rC]:
      rC -= 1
    t = Lr[rC]
    if A2[k][2] > A2[t][2]:
      L.append((A[k] + A[t] + (k - t) * D, t, k))
  
  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: Wrong Answer

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

  A2 = [[A[i], i, 0] for i in range(N)]
  A2.sort()
  for i in range(N):
    A2[i][2] = i
  A2.sort(key = lambda x: x[1])
  A2 = tuple(A2)
  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 = 0
  for i in range(N-1):
    if i >= Ll[lC]:
      lC -= 1
    t = Ll[lC]
    if A2[i][2] > A2[t][2]: 
      L.append((A[i] + A[t] + (t - i) * D, i, t))
    k = i + 1
    if k > Lr[rC+1]:
      rC += 1
    t = Lr[rC]
    if A2[k][2] > A2[t][2]:
      L.append((A[k] + A[t] + (k - t) * D, t, k))
  
  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: Wrong Answer

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 - 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 = 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
for i in range(N-1):
  if i >= Ll[lC]:
    lC -= 1
  for j in range(lC, -len(Ll) - 1, -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, 0, -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: Wrong Answer

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 = (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
Lr.append(N)

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

L = []
lC = -1
rC = 1
for i in range(N-1):
  if i >= Ll[lC]:
    lC -= 1
  t = Ll[lC]
  L.append((A[i] + A[t] + (t - i) * D, i, t))
  k = i + 1
  if k > Lr[rC]:
    rC += 1
  t = Lr[rC-1]
  L.append((A[k] + A[t] + (k - t) * D, t, k))
 
L = list(set(L))  
L.sort()
L = tuple(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: Wrong Answer

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

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)

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


N,D=map(int,input().split())
A=[int(i) for i in input().split()]
lefttree = BIT(N)
dd={}
table=[]
for i in range(N):
    lefttree.add(i+1,A[i]+(N-1-i)*D)
    dd[A[i]+(N-1-i)*D]=i
    if i>0:
        s=lefttree.search(i)
        y=dd[s]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
#print(table)
righttree = BIT(N)
dr={}
for i in range(N-1,-1,-1):
    righttree.add(N-i,A[i]+i*D)
    dr[A[i]+i*D]=i
    if i<N-1:
        s=righttree.search(N-1-i)
        #print(i, dr,s)
        y=dr[s]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
#print(table)

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