Language: C++

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e17;

struct SE {
  int n, op;
  vector<long long> v;
  
  void Init(int _n, int _op) {
    n = _n;
    op = _op;
    v.resize(n * 4 + 1, INF);
  }
  
  void Set(int t, int l, int r, int x, long long _v) {
    if (l == r) {
      v[t] = _v + l * op;
      return;
    }
    int md = (l + r) >> 1;
    if (x <= md) Set(t << 1, l, md, x, _v);
    else Set(t << 1 | 1, md + 1, r, x, _v);
    v[t] = min(v[t << 1], v[t << 1 | 1]);
  }

  long long Query(int t, int l, int r, int L, int R) {
    if (L <= l && r <= R) return v[t];
    int md = (l + r) >> 1, re = INF;
    if (L <= md) re = min(re, Query(t << 1, l, md, L, R));
    if (R > md) re = min(re, Query(t << 1 | 1, md + 1, r, L, R));
    return re;
  }
} lt, rt;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n, nq, a, b;
  long long tag = 0;
  cin >> n >> nq >> a >> b;
  vector<int> x(nq);
  vector<long long> dp(n + 1, INF);
  cin >> x[0];

  lt.Init(n, -1);
  rt.Init(n, 1);
  lt.Set(1, 1, n, a, abs(x[0] - b));
  lt.Set(1, 1, n, b, abs(x[0] - a));
  rt.Set(1, 1, n, a, abs(x[0] - b));
  rt.Set(1, 1, n, b, abs(x[0] - a));
  dp[a] = min(dp[a], abs(x[0] - b));
  dp[b] = min(dp[b], abs(x[0] - a));
  
  for (int i = 1; i < nq; ++i) {
    cin >> x[i];
    long long lck = lt.Query(1, 1, n, 1, x[i]) + x[i] + tag;
    long long rck = rt.Query(1, 1, n, x[i], n) - x[i] + tag;
    tag += abs(x[i] - x[i - 1]);
    if (dp[x[i - 1]] + tag > min(lck, rck)) {
      dp[x[i - 1]] = min(lck, rck) - tag;
      lt.Set(1, 1, n, x[i - 1], dp[x[i - 1]]);
      rt.Set(1, 1, n, x[i - 1], dp[x[i - 1]]);
    }
  }

  long long ans = INF;
  for (int i = 1; i <= n; ++i) {
    ans = min(ans, dp[i]);
  }
  cout << ans + tag << endl;
  
  return 0;
}


Compiler output:
a.cc: In member function 'long long int SE::Query(int, int, int, int, int)':
a.cc:30:33: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   30 |     int md = (l + r) >> 1, re = INF;
      |                                 ^~~
a.cc:31:26: error: no matching function for call to 'min(int&, long long int)'
   31 |     if (L <= md) re = min(re, Query(t << 1, l, md, L, R));
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:31:26: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   31 |     if (L <= md) re = min(re, Query(t << 1, l, md, L, R));
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:31:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   31 |     if (L <= md) re = min(re, Query(t << 1, l, md, L, R));
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:32:25: error: no matching function for call to 'min(int&, long long int)'
   32 |     if (R > md) re = min(re, Query(t << 1 | 1, md + 1, r, L, R));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:32:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   32 |     if (R > md) re = min(re, Query(t << 1 | 1, md + 1, r, L, R));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:32:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   32 |     if (R > md) re = min(re, Query(t << 1 | 1, md + 1, r, L, R));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc: In function 'int main()':
a.cc:54:14: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, int)'
   54 |   dp[a] = min(dp[a], abs(x[0] - b));
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:54:14: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   54 |   dp[a] = min(dp[a], abs(x[0] - b));
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:54:14: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   54 |   dp[a] = min(dp[a], abs(x[0] - b));
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~
a.cc:55:14: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, int)'
   55 |   dp[b] = min(dp[b], abs(x[0] - a));
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:55:14: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   55 |   dp[b] = min(dp[b], abs(x[0] - a));
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:55:14: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   55 |   dp[b] = min(dp[b], abs(x[0] - a));
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~