Language: C++

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
const int BIT = 29;
const int mod = 1e9 + 7;
int seg[4 * N];
int n, d, par[N];
long long a[N];
vector<int> sz[N];
void update(int node, int start, int end, int idx){
    if(start > end || idx < start || end < idx) return;
    if(start == end){
        seg[node][0] = idx;
        seg[node][1] = idx;
        return;
    }
    int mid = (start + end) >> 1;
    update(node << 1, start, mid, idx);
    update(node << 1 | 1, mid + 1, end, idx);
    if(a[seg[node << 1][typ]][typ] <= a[seg[node << 1 | 1][typ]][typ]){
        seg[node][typ] = seg[node << 1][typ];
    }else{
        seg[node][typ] = seg[node << 1 | 1][typ];
    }
}
int query(int node, int start, int end, int l, int r, int typ){
    if(start > end || r < start || end < l) return 0;
    if(l <= start && end <= r){
        return seg[node][typ];
    }
    int mid = (start + end) >> 1;
    int q1 = query(node << 1, start, mid, l, r, typ);
    int q2 = query(node << 1 | 1, mid + 1, end, l, r, typ);
    if(a[q1][typ] <= a[q2][typ]){
        return q1;
    }else{
        return q2;
    }
}
int main(){
    set<pair<int, int> > s;
    long long ans = 0;
    scanf("%d %d", &n, &d);
    a[0][0] = a[0][1] = 1e16;
    for(int i = 1; i <= n; i++){
        int val;
        scanf("%d", &val);
        a[i][0] = val - 1LL * i * d;
        a[i][1] = val + 1LL * i * d;
    }
    for(int i = 1; i <= n; i++){
        par[i] = i;
        sz[i].push_back(i);
        update(1, 1, n, i);
        s.insert({sz[i].size(), i});
    }
    int edge = n - 1;
    while(edge--){
        int c = (s.begin()) -> second;
        for(int i : sz[c]){
            update(1, 1, n, 0);
        }
        long long mini = 2e9;
        int idx;
        s.erase(s.find({sz[c].size(), c}));
        s.erase(s.find({sz[p].size(), p}));
        for(int i : sz[c]){
            int q1 = query(1, 1, n, 1, i - 1, 0);
            int q2 = query(1, 1, n, i + 1, n, 1);
            long long res = a[i][1] + a[q1][0];
            if(res < mini){
                mini = res;
                idx = q1;
            } 
            res = a[i][0] + a[q2][1];
            if(res < mini){
                mini = res;
                idx = q2;
            } 
        }
        ans += mini;
        int p = par[idx];
        while(sz[c].size()){
            int i = sz[c].back();
            update(1, 1, n, i);
            sz[p].push_back(i);
            par[i] = p;
            sz[c].pop_back();
        }
        s.insert({sz[p].size(), p});
    }
    printf("%lld\n", ans);
    return 0;
}

Compiler output:
a.cc: In function 'void update(int, int, int, int)':
a.cc:13:18: error: invalid types 'int[int]' for array subscript
   13 |         seg[node][0] = idx;
      |                  ^
a.cc:14:18: error: invalid types 'int[int]' for array subscript
   14 |         seg[node][1] = idx;
      |                  ^
a.cc:20:25: error: 'typ' was not declared in this scope
   20 |     if(a[seg[node << 1][typ]][typ] <= a[seg[node << 1 | 1][typ]][typ]){
      |                         ^~~
a.cc: In function 'int query(int, int, int, int, int, int)':
a.cc:29:25: error: invalid types 'int[int]' for array subscript
   29 |         return seg[node][typ];
      |                         ^
a.cc:34:13: error: invalid types 'long long int[int]' for array subscript
   34 |     if(a[q1][typ] <= a[q2][typ]){
      |             ^
a.cc:34:27: error: invalid types 'long long int[int]' for array subscript
   34 |     if(a[q1][typ] <= a[q2][typ]){
      |                           ^
a.cc: In function 'int main()':
a.cc:44:9: error: invalid types 'long long int[int]' for array subscript
   44 |     a[0][0] = a[0][1] = 1e16;
      |         ^
a.cc:44:19: error: invalid types 'long long int[int]' for array subscript
   44 |     a[0][0] = a[0][1] = 1e16;
      |                   ^
a.cc:48:13: error: invalid types 'long long int[int]' for array subscript
   48 |         a[i][0] = val - 1LL * i * d;
      |             ^
a.cc:49:13: error: invalid types 'long long int[int]' for array subscript
   49 |         a[i][1] = val + 1LL * i * d;
      |             ^
a.cc:66:28: error: 'p' was not declared in this scope
   66 |         s.erase(s.find({sz[p].size(), p}));
      |                            ^
a.cc:66:23: error: no matching function for call to 'std::set<std::pair<int, int> >::find(<brace-enclosed initializer list>)'
   66 |         s.erase(s.find({sz[p].size(), p}));
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/set:63,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:158,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_set.h:806:9: note: candidate: 'template<class _Kt> decltype (std::set<_Key, _Compare, _Alloc>::iterator{((std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::set<_Key, _Compare, _Alloc>::find(const _Kt&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  806 |         find(const _Kt& __x)
      |         ^~~~
/usr/include/c++/14/bits/stl_set.h:806:9: note:   template argument deduction/substitution failed:
a.cc:66:23: note:   couldn't deduce template parameter '_Kt'
   66 |         s.erase(s.find({sz[p].size(), p}));
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_set.h:812:9: note: candidate: 'template<class _Kt> decltype (std::set<_Key, _Compare, _Alloc>::const_iterator{((const std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::set<_Key, _Compare, _Alloc>::find(const _Kt&) const [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  812 |         find(const _Kt& __x) const
      |         ^~~~
/usr/include/c++/14/bits/stl_set.h:812:9: note:   template argument deduction/substitution failed:
a.cc:66:23: note:   couldn't deduce template parameter '_Kt'
   66 |         s.erase(s.find({sz[p].size(), p}));
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_set.h:796:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::find(const key_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; key_type = std::pair<int, int>]'
  796 |       find(const key_type& __x)
      |       ^~~~
/usr/include/c++/14/bits/stl_set.h:796:28: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::set<std::pair<int, int> >::key_type&' {aka 'const std::pair<int, int>&'}
  796 |       find(const key_type& __x)
      |            ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_set.h:800:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::const_iterator std::set<_Key, _Compare, _Alloc>::find(const key_type&) const [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; key_type = std::pair<int, int>]'
  800 |       find(const key_type& __x) const
      |       ^~~~
/usr/include/c++/14/bits/stl_set.h:800:28: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::set<std::pair<int, int> >::key_type&' {aka 'const std::pair<int, int>&'}
  800 |       find(const key_type& __x) const
      |            ~~~~~~~~~~~~~~~~^~~
a.cc:70:33: error: invalid types 'long long int[int]' for array subscript
   70 |             long long res = a[i][1] + a[q1][0];
      |                                 ^
a.cc:70:44: error: invalid types 'long long int[int]' for array subscript
   70 |             long long res = a[i][1] + a[q1][0];
      |                                            ^
a.cc:75:23: error: invalid types 'long long int[int]' for array subscript
   75 |             res = a[i][0] + a[q2][1];
      |                       ^
a.cc:75:34: error: invalid types 'long long int[int]' for array subscript
   75 |             res = a[i][0] + a[q2][1];
      |                                  ^
a.cc:90:17: error: no matching function for call to 'std::set<std::pair<int, int> >::insert(<brace-enclosed initializer list>)'
   90 |         s.insert({sz[p].size(), p});
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_set.h:568:9: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  568 |         insert(_InputIterator __first, _InputIterator __last)
      |         ^~~~~~
/usr/include/c++/14/bits/stl_set.h:568:9: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_set.h:511:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<int, int> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::rebind<std::pair<int, int> >; typename _Alloc::value_type = std::pair<int, int>; value_type = std::pair<int, int>]'
  511 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_set.h:511:32: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::set<std::pair<int, int> >::value_type&' {aka 'const std::pair<int, int>&'}
  511 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_set.h:520:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(value_type&&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<int, int> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::rebind<std::pair<int, int> >; typename _Alloc::value_type = std::pair<int, int>; value_type = std::pair<int, int>]'
  520 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_set.h:520:27: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
  520 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_set.h:548:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(const_iterator, const value_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<in