Language: C++

#include <iostream>
#include <vector>
#include <cassert>
#include <utility>

using namespace std;

class UnionFind
{
public:
    vector<int> parent;
    vector<int> rank;
    
    UnionFind(int n): parent(n), rank(n)
    {
        for(int i=0;i<n;i++)
            parent[i] = i,
            rank[i] = 0;
    }

    int root(int x)
    {
        return parent[x]==x ? x : parent[x] = root(parent[x]);
    }

    bool same(int x, int y)
    {
        return root(x)==root(y);
    }

    void unite(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x != y)
        {
            if (rank[x] < rank[y])
                parent[x] = y;
            else
                parent[y] = x;
            if (rank[x]==rank[y])
                rank[x]++;
        }
    }
};

int main()
{
    int N;
    cin>>N;
    long long D;
    cin>>D;
    vector<long long> A(N);
    for (long long &a: A)
        cin>>a;

    long long ans = 0;
    UnionFind UF(N);
    int n = 0;
    vector<int> F(N), B(N);
    vector<pair<int,int>> X(N);

    while (n<N-1)
    {
        int f1 = -1;
        int f2 = -1;
        for (int i=0; i<N; i++)
        {
            F[i] = f1 == -1 || UF.root(f1)!=UF.root(i) ? f1 : f2;

            if (f1==-1)
                f1 = i;
            else if (A[i] <= (i-f1)*D+A[f1])
            {
                if (UF.root(i)!=UF.root(f1))
                    f2 = f1;
                f1 = i;
            }

            if (UF.root(i) != UF.root(f1) &&
                (f2==-1 || A[i]<=(i-f2)*D+A[f2]))
                f2 = i;

            //assert(f1==-1 || f2==-1 || UF.root(f1)!=UF.root(f2));
        }

        int b1 = -1;
        int b2 = -1;
        for (int i=N-1; i>=0; i--)
        {
            B[i] = b1 == -1 || UF.root(b1)!=UF.root(i) ? b1 : b2;

            if (b1==-1)
                b1 = i;
            else if (A[i] <= (b1-i)*D+A[b1])
            {
                if (UF.root(i)!=UF.root(b1))
                    b2 = b1;
                b1 = i;
            }

            if (UF.root(i) != UF.root(b1) &&
                (b2==-1 || A[i]<=(b2-i)*D+A[b2]))
                b2 = i;

            //assert(b1==-1 || b2==-1 || UF.root(b1)!=UF.root(b2));
        }

        for (int i=0; i<N; i++)
            X[i] = make_pair(-1,-1);

        for (int i=0; i<N; i++)
        {
            /*
            int c = -1;
            if (F[i]==-1 && B[i]!=-1)
                c = B[i];
            if (F[i]!=-1 && B[i]==-1)
                c = F[i];
            if (F[i]!=-1 && B[i]!=-1)
            {
                if ((i-F[i])*D + A[F[i]] + A[i] < (B[i]-i)*D + A[B[i]] + A[i])
                    c = F[i];
                else
                    c = B[i];
            }
            */

            if (F[i] != -1)
            {
                int r = UF.root(i);
                if (X[r].first == -1 ||
                    (i-F[i])*D + A[i] + A[F[i]] <
                    abs(X[r].first-X[r].second)*D + A[X[r].first] + A[X[r].second])
                {
                    X[r] = make_pair(F[i], i);
                }
            }

            if (B[i] != -1)
            {
                int r = UF.root(i);
                if (X[r].first == -1 ||
                    (B[i]-i)*D + A[i] + A[B[i]] <
                    abs(X[r].first-X[r].second)*D + A[X[r].first] + A[X[r].second])
                {
                    X[r] = make_pair(i, B[i]);
                }
            }

            for (int i=0; i <N; i++)
            {
                if (X[i].first != -1 && UF.root(X[i].first)!=UF.root(X[i].second))
                {
                UF.unite(X[i].first, X[i].second);
                n++;
                ans += abs(X[i].first-X[i].second)*D + A[X[i].first] + A[X[i].second];
            }
        }
        cout<<endl;
    }

    cout<<ans<<endl;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:164:2: error: expected '}' at end of input
  164 | }
      |  ^
a.cc:48:1: note: to match this '{'
   48 | {
      | ^