Language: C++

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define MAX_V 400010
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<typename A, size_t NNN, typename T>
void Fill(A (&array)[NNN], const T &val){
    fill( (T*)array, (T*)(array+NNN), val );
}
#define N 100100
#define INF 1e9+7
ll MOD=1e9+7;

ll n,m;
ll a[N],b[N],c[N];
int pre[N],suf[N];
ll ans[N];
int used[N];
template<typename T>
struct BIT{
    vector<T> data;

    BIT(int size){
        data.assign(++size,LLINF);
    }
    T querry(int k){
        T ret=LLINF;
        for(++k;k>0;k-=k&-k) ret=min(ret,data[k]);
        return (ret);
    }
    void add(int k,T x){
        for(++k;k<data.size();k+=k&-k)data[k]=min(data[k],x);
    }
};
vector<ll> v[N];
struct UnionFind{
    vector<int> par,sizes;
    UnionFind(int n):par(n+1),sizes(n+1,1){
        rep2(i,1,n)par[i]=i;
    }
    int find(int x){
        return (x==par[x]?x:par[x]=find(par[x]));
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return ;
        if(sizes[x]<sizes[y]){
            swap(x,y);
        }
        par[y]=x;
        sizes[x]+=sizes[y];
    }
    bool same(int x,int y) return (find(x)==find(y));
    int size(int x) return sizes[find(x)];
};
main(){
    n=in();
    ll d=in();
    rep(i,n)a[i]=lin();
    rep(i,n){
        b[i]=a[i]+i*d;
        c[i]=a[i]-i*d;
    }
    ll mem=LLINF;
    int now=0;
    rep(i,n){
        if(c[i]<mem){
            pre[i]=now=i;
            mem=c[i];
        }
        else pre[i]=now;
    }
    now=n-1;
    mem=LLINF;
    rep3(i,n-1,0){
        if(b[i]<mem){
            mem-b[i];
            suf[i]=now=i;
        }
        else suf[i]=now;
    }
    UnionFind u(n);
    rep(i,n){
        ll r;
        int s,t;
        if(i==n-1){
            r=LLINF;
            s=-1;
        }
        else {
            r=b[suf[i+1]];
            s=suf[i+1];
        }
        ll l;
        if(i==0){
            l=LLINF;t=-1;
        }
        else {
            l=c[pre[i-1]];t=pre[i-1];
        }
        r=r+a[i]-d*i;
        l=l+a[i]+d*i;
        while(t>0&&u.same(i,t)){
            t=pre[t-1];
            if(t==0&&u.same(i,t))t=-1;
        }
        while(s<n-1&&same(i,s)){
            s=suf[s+1];
            if(s==n-1&&u.same(i,t))s=-1;
        }
        if(s==-1&&t==-1){
            ans[i].pb(LLINF);
        }
        else if(s==-1){
            ans[i].pb(c[t]+a[i]+d*i);
            u.unite(i,t);
        }
        else if(t==-1){
            ans[i].pb(b[s]+a[i]-d*i);
            u.unite(i,s);
        }
        else if(c[t]+a[i]+d*i>b[s]+a[i]-d*i){
            ans[i].pb(b[s]+a[i]-d*i);
            u.unite(i,s);
        }
        else {
            ans[i].pb(c[t]+a[i]+d*i);
            u.unite(i,t);
        }

    }
    sort(ans,ans+n);
    ll sum=0;
    rep(i,n-1){
        sum+=ans[i];
    }
    cout<<sum;
}


Compiler output:
a.cc: In constructor 'BIT<T>::BIT(int)':
a.cc:60:28: error: 'LLINF' was not declared in this scope; did you mean 'INF'?
   60 |         data.assign(++size,LLINF);
      |                            ^~~~~
      |                            INF
a.cc: In member function 'T BIT<T>::querry(int)':
a.cc:63:15: error: 'LLINF' was not declared in this scope; did you mean 'INF'?
   63 |         T ret=LLINF;
      |               ^~~~~
      |               INF
a.cc: In member function 'bool UnionFind::same(int, int)':
a.cc:89:35: error: expected identifier before '(' token
   89 |     bool same(int x,int y) return (find(x)==find(y));
      |                                   ^
a.cc:89:28: error: named return values are no longer supported
   89 |     bool same(int x,int y) return (find(x)==find(y));
      |                            ^~~~~~
a.cc:89:53: error: expected '{' at end of input
   89 |     bool same(int x,int y) return (find(x)==find(y));
      |                                                     ^
a.cc:89:53: warning: no return statement in function returning non-void [-Wreturn-type]
a.cc: In member function 'int UnionFind::size(int)':
a.cc:90:21: error: named return values are no longer supported
   90 |     int size(int x) return sizes[find(x)];
      |                     ^~~~~~
a.cc:90:42: error: expected '{' at end of input
   90 |     int size(int x) return sizes[find(x)];
      |                                          ^
a.cc:90:42: warning: no return statement in function returning non-void [-Wreturn-type]
a.cc: At global scope:
a.cc:92:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main(){
      | ^~~~
a.cc: In function 'int main()':
a.cc:100:12: error: 'LLINF' was not declared in this scope; did you mean 'INF'?
  100 |     ll mem=LLINF;
      |            ^~~~~
      |            INF
a.cc:143:22: error: 'same' was not declared in this scope
  143 |         while(s<n-1&&same(i,s)){
      |                      ^~~~
a.cc:31:12: error: request for member 'push_back' in 'ans[i]', which is of non-class type 'long long int'
   31 | #define pb push_back
      |            ^~~~~~~~~
a.cc:148:20: note: in expansion of macro 'pb'
  148 |             ans[i].pb(LLINF);
      |                    ^~
a.cc:31:12: error: request for member 'push_back' in 'ans[i]', which is of non-class type 'long long int'
   31 | #define pb push_back
      |            ^~~~~~~~~
a.cc:151:20: note: in expansion of macro 'pb'
  151 |             ans[i].pb(c[t]+a[i]+d*i);
      |                    ^~
a.cc:31:12: error: request for member 'push_back' in 'ans[i]', which is of non-class type 'long long int'
   31 | #define pb push_back
      |            ^~~~~~~~~
a.cc:155:20: note: in expansion of macro 'pb'
  155 |             ans[i].pb(b[s]+a[i]-d*i);
      |                    ^~
a.cc:31:12: error: request for member 'push_back' in 'ans[i]', which is of non-class type 'long long int'
   31 | #define pb push_back
      |            ^~~~~~~~~
a.cc:159:20: note: in expansion of macro 'pb'
  159 |             ans[i].pb(b[s]+a[i]-d*i);
      |                    ^~
a.cc:31:12: error: request for member 'push_back' in 'ans[i]', which is of non-class type 'long long int'
   31 | #define pb push_back
      |            ^~~~~~~~~
a.cc:163:20: note: in expansion of macro 'pb'
  163 |             ans[i].pb(c[t]+a[i]+d*i);
      |                    ^~