Language: C++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

ll N;
ll D;
vector<pair<ll, ll>> A;

struct UnionFind {
    vector<int> data;

    UnionFind(int size) : data(size, -1) {}

    UnionFind() {}

    bool unionSet(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
            //cout << x << " " << y << endl;
        }
        return x != y;
    }

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

    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }

    int size(int x) {
        return -data[root(x)];
    }
};


UnionFind uf;

set<pair<ll, ll> > S;

void add(ll x, ll v, ll dsum) {
    S.insert({v - dsum, A[x].second});
}

long long INF = 1e18;

pair<ll, ll> find_min(ll x, ll dsum) {
    pair<ll, ll> r;
    auto it = S.begin();
    while (it != S.end()) {
        if (uf.findSet(A[x].second, it->second)) {
            ++it;
        } else {
            r = *it;
            break;
        }
    }
//    hoge[uf.root(A[x].second)] = it;
    if (it == S.end()) return {INF, INF};
    return {r.first + dsum + A[x].first, r.second};
}

void init() {
    S.clear();
}

bool one_step(ll &ans) {
    init();
    vector<pair<ll,pair<ll, ll>>> seq;

    for (int i = 0; i < A.size(); i++) {
        auto r = find_min(i, i * D);
        seq.emplace_back(r.first, r.second, i);
        add(i, A[i].first, i * D);
    }

    init();
    reverse(A.begin(), A.end());
    {
        for (int i = 0; i < A.size(); i++) {
            auto r = find_min(i, i * D);
            seq.emplace_back(r.first, A[i].second, r.second);
            add(i, A[i].first, i * D);
        }
    }
    reverse(A.begin(), A.end());

    sort(seq.begin(), seq.end());
    for(auto i : seq ){
        if( uf.findSet(i.second.))
    }
    return false;
}

void fake_solve() {

    uf = UnionFind(N);
    ll ans = 0;
    while (true) {
        if (!one_step(ans)) break;
        //cout << "===" << endl;
    }
    cout << ans << endl;


}

void solve() {
    fake_solve();

//  UnionFind uf(N);
//  int ans = 0;
//  while(true) {
//    vector<pair<int, pair<int, int>>> es[N];
//    for (int i = 0; i < N; i++) {
//      for (int j = 0; j < N; j++) {
//        if (i != j && uf.findSet(i, j) == 0) {
//          es[uf.root(i)].push_back({abs(i - j) * D + A[i] + A[j], {i, j}});
//        }
//      }
//    }
//    bool upd = false;
//    for(int i = 0 ; i < N ; i++){
//      if( uf.root(i) == i ){
//        sort(es[i].begin(), es[i].end());
//        if( es[i].size() > 0 ){
//          ans += es[i].front().first;
//          uf.unionSet(es[i].front().second.first, es[i].front().second.second);
//          cout << es[i].front().second.first << "-"  << es[i].front().second.second << endl;
//          upd = true;
//        }
//      }
//    }
//    cout << "====" << endl;
//    if(!upd) break;
//  }

//  int ans = 0;
//  for(int i = 0 ; i < es.size() ; i++){
//    if( uf.unionSet(es[i].second.first, es[i].second.second)){
//      cout << es[i].second.first << " " << es[i].second.second << endl;
//      ans += es[i].first;
//    }
//  }
//    cout << ans << endl;


    //cout << "No submit" << endl;
}

void input() {
    N = ll();
    scanf("%lld", &N);
    D = ll();
    scanf("%lld", &D);
    A = vector<pair<ll, ll>>(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i].first);
        A[i].second = i;
    }
}

int main() {
    input();
    solve();
    return 0;
}


Compiler output:
a.cc: In function 'bool one_step(ll&)':
a.cc:98:33: error: expected unqualified-id before ')' token
   98 |         if( uf.findSet(i.second.))
      |                                 ^
a.cc:99:5: error: expected primary-expression before '}' token
   99 |     }
      |     ^
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/c++allocator.h:33,
                 from /usr/include/c++/14/bits/allocator.h:46,
                 from /usr/include/c++/14/string:43,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/new_allocator.h: In instantiation of 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::pair<long long int, std::pair<long long int, long long int> >; _Args = {long long int&, long long int&, int&}; _Tp = std::pair<long long int, std::pair<long long int, long long int> >]':
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<long long int, std::pair<long long int, long long int> >; _Args = {long long int&, long long int&, int&}; _Tp = std::pair<long long int, std::pair<long long int, long long int> >; allocator_type = std::allocator<std::pair<long long int, std::pair<long long int, long long int> > >]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/vector.tcc:117:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {long long int&, long long int&, int&}; _Tp = std::pair<long long int, std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, std::pair<long long int, long long int> > >; reference = std::pair<long long int, std::pair<long long int, long long int> >&]'
  117 |             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  118 |                                      std::forward<_Args>(__args)...);
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:81:25:   required from here
   81 |         seq.emplace_back(r.first, r.second, i);
      |         ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/new_allocator.h:191:11: error: no matching function for call to 'std::pair<long long int, std::pair<long long int, long long int> >::pair(long long int&, long long int&, int&)'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:913:28: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<long long int, long long int>, _U2>::value)), long long int, std::pair<long long int, long long int> >::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<long long int, long long int>, _U2>::value)), long long int, std::pair<long long int, long long int> >::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<long long int, long long int>]'
  913 |         explicit constexpr pair(pair<_U1, _U2>&& __p)
      |                            ^~~~
/usr/include/c++/14/bits/stl_pair.h:913:28: note:   candidate expects 1 argument, 3 provided
/usr/include/c++/14/bits/stl_pair.h:902:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<long long int, long long int>, _U2>::value)), long long int, std::pair<long long int, long long int> >::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<long long int, long long int>, _U2>::value)), long long int, std::pair<long long int, long long int> >::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<long long int, long long int>]'
  902 |         constexpr pair(pair<_U1, _U2>&& __p)
      |                   ^~~~
/usr/include/c++/14/bits/stl_pair.h:902:19: note:   candidate expects 1 argument, 3 provided
/usr/include/c++/14/bits/stl_pair.h:891:28: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && (! _ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<long long int, long long int>]'
  891 |         explicit constexpr pair(_U1&& __x, _U2&& __y)
      |                            ^~~~
/usr/include/c++/14/bits/stl_pair.h:891:28: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/14/bits/stl_pair.h:881:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && _ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<long long int, long long int>]'
  881 |         constexpr pair(_U1&& __x, _U2&& __y)
      |                   ^~~~
/usr/include/c++/14/bits/stl_pair.h:881:19: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/14/bits/stl_pair.h:869:9: note: candidate: 'template<class _U2, typename std::enable_if<std::__and_<std::is_pointer<long long int>, std::__not_<std::is_reference<_Tp> >, std::is_constructible<std::pair<long long int, long long int>, _U2>, std::__not_<std::is_constructible<std::pair<long long int, long long int>, const _U1&> >, std::__not_<std::is_convertible<_U2, std::pair<long long int, long long int> > > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(__zero_as_null_pointer_constant, _U2&&, ...) [with typename std::enable_if<std::__and_<std::is_pointer<_Tp>, std::__not_<std::is_reference<_U1> >, std::is_constructible<_T2, _U2>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::__not_<std::is_convertible<_U2, _T2> > >::value, bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<long long int, long long int>]'
  869 |         pair(__zero_as_null_pointer_constant, _U2&& __y, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:869:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:866:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  866 |                              bool> = false>
      |                                      ^~~~~
/usr/include/c++/14/bits/stl_pair.h:856:9: note: candidate: 'template<class _U2, typename std::enable_if<std::__and_<std::is_pointer<long long int>, std::__not_<std::is_reference<_Tp> >, std::is_constructible<std::pair<long long int, long long int>, _U2>, std::__not_<std::is_constructible<std::pair<long long int, long long int>, const _U1&> >, std::is_convertible<_U2, std::pair<long long int, long long int> > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(__zero_as_null_pointer_constant, _U2&&, ...) [with typename std::enable_if<std::__and_<std::is_pointer<_Tp>, std::__not_<std::is_reference<_U1> >, std::is_constructible<_T2, _U2>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::is_convertible<_U2, _T2> >::value, bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<long long int, long long int>]'
  856 |         pair(__zero_as_null_pointer_constant, _U2&& __y, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:856:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:853:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  853 |                              bool> = true>
      |                                      ^~~~
/usr/include/c++/14/bits/stl_pair.h:843:9: note: candidate: 'template<class _U1, typename std::enable_if<std::__and_<std::__not_<std::is_reference<_Tp> >, std::is_pointer<std::pair<long long int, long long int> >, std::is_constructible<long long int, _U1>, std::__not_<std::is_constructible<long long int, const _U1&> >, std::__not_<std::is_convertible<_U1, long long int> > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, __zero_as_null_pointer_constant, ...) [with typename std::enable_if<std::__and_<std::__not_<std::is_reference<_U1> >, std::is_pointer<_T2>, std::is_const