Language: C++

/*
ID: htc9811
LANG: C++
TASK:
*/
#define int long long
#include<stdio.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<ctime>
#include<complex>
#include<list>
#include<limits.h>
using namespace std;

const int N=2e5+5;
int n,cur;
long long a[N];
long long d,ans;

struct Seg{
	long long length;
	int x,y;
	Seg(){};
	Seg(long long length,int x,int y):length(length),x(x),y(y){};
};

struct UF{
	int p[N],rnk[N];
	void init(int n){
		for(int i=0;i<n;i++) p[i]=i;
		for(int i=0;i<n;i++) rnk[i]=1;
	}
	int fp(int x){
		return x==p[x]?x:p[x]=fp(p[x]);
	}
	void un(int x,int y){
		if(rnk[x]>rnk[y]) p[y]=x;
		if(rnk[x]<rnk[y]) p[x]=y;
		if(rnk[x]==rnk[y]) p[x]=y,rnk[y]++;
	}
};

inline bool comp(Seg &x,Seg &y){
	return x.length<y.length;
}

vector<Seg> seg;
UF uf;

void solve(int left,int right){
	if(left>=right) return;
	int middle=(left+right)>>1;
	int pl=0;
	long long vl=a[left];
	for(int i=left+1;i<=middle;i++){
		long long cv=a[i]-d*i;
		if(cv<vl){
			vl=cv;
			pl=i;
		}
	}
	int pr=middle+1;
	long long vr=a[middle+1]+d*(middle+1);
	for(int i=middle+1;i<=right;i++){
		long long cv=a[i]+d*i;
		if(cv<vr){
			vr=cv;
			pr=i;
		}
	}
	for(int i=left;i<=middle;i++) seg.push_back(Seg(a[i]-d*i+vr,i,pr));
	for(int i=middle+1;i<=right;i++) seg.push_back(Seg(a[i]+d*i+vl,pl,i));
	solve(left,middle);
	solve(middle+1,right);
}

signed main(){
//	freopen("cc.in","r",stdin);
//	freopen("cc1.out","w",stdout);
	scanf("%lld%lld",&n,&d);
	uf.init(n);
	for(int i=0;i<n;i++) scanf("%lld",a+i);
	solve(0,n-1);
	sort(seg.begin(),seg.end(),comp);
	for(int i=1;i<n;i++){
		while(true){
			int nx=seg[cur].x;
			int ny=seg[cur].y;
			long long len=seg[cur++].length;
			nx=uf.fp(nx);
			ny=uf.fp(ny);
			if(nx!=ny){
				uf.un(nx,ny);
				ans+=len;
				break;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Compiler output:
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long' and 'short' specified together
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long' and 'short' specified together
    6 | #define int long long
      |             ^~~~
a.cc:6:13: error: 'long' and 'short' specified together
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long' and 'short' specified together
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:13: error: 'long long long' is too long for GCC
    6 | #define int long long
      |             ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
a.cc:6:18: error: 'long long long' is too long for GCC
    6 | #define int long long
      |                  ^~~~
In file included from /usr/include/c++/14/bits/char_traits.h:50,
                 from /usr/include/c++/14/string:42,
                 from a.cc:8:
/usr/include/c++/14/type_traits:404:12: error: redefinition of 'struct std::__is_integral_helper<long long int>'
  404 |     struct __is_integral_helper<long long>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/type_traits:388:12: note: previous definition of 'struct std::__is_integral_helper<long long int>'
  388 |     struct __is_integral_helper<int>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/type_traits:408:12: error: redefinition of 'struct std::__is_integral_helper<long long unsigned int>'
  408 |     struct __is_integral_helper<unsigned long long>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/type_traits:392:12: note: previous definition of 'struct std::__is_integral_helper<long long unsigned int>'
  392 |     struct __is_integral_helper<unsigned int>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/type_traits:1605:43: error: no matching function for call to 'declval<void*>()'
 1605 |         noexcept(::new(std::declval<void*>()) _Tp(std::declval<_Args>()...))
      |                        ~~~~~~~~~~~~~~~~~~~^~
/usr/include/c++/14/type_traits:973:10: note: candidate: 'template<class _Tp> decltype (__declval<_Tp>(0)) std::declval()'
  973 |     auto declval() noexcept -> decltype(__declval<_Tp>(0));
      |          ^~~~~~~
/usr/include/c++/14/type_traits:973:10: note:   template argument deduction/substitution failed:
/usr/include/c++/14/type_traits: In substitution of 'template<class _Tp> decltype (__declval<_Tp>(0)) std::declval() [with _Tp = void*]':
/usr/include/c++/14/type_traits:1605:36:   required from here
 1605 |         noexcept(::new(std::declval<void*>()) _Tp(std::declval<_Args>()...))
      |                        ~~~~~