Submission #1873067

---

Source Code Expand

#include<bits/stdc++.h>
#define out(x) cerr << #x << " = " << x << "\n"
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
  x = 0;char c = getchar();bool f = 0;
  for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
  for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
  if(f) x = -x;
}
#define c(a, b) memset(a, b, sizeof(a))
const int N = 3e5 + 233, inf = 1e9 + 233;
int n, Q, x, y, a[N], ans, tag, res[N];
struct T {
  int tr[N << 2], M;
  inline void init() {
    for(M = 1; M <= n + 1; M <<= 1);
    memset(tr, 38, sizeof(tr));
  }
  inline void ps(int &x, int y) {if(x > y) x = y;}
  inline void in(int u, int v) {
    for(ps(tr[u += M], v), u >>= 1; u; ps(tr[u >>= 1], v));
  }
  inline int q(int s, int t, int ans = inf) {
    for(s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
      if(~s & 1) ps(ans, tr[s ^ 1]);
      if(t & 1) ps(ans, tr[t ^ 1]);
    }
    return ans;
  }
}tr1, tr2;
  
inline void add2(int pos, int now) {
  now += (n - (pos - 1));
  // cout << "tr2 " << pos << " " << now << "\n";
  tr2.in(pos, now);
} 

inline void add1(int pos, int now) {
  now += pos; 
  // cout << "tr1 " << pos << " " << now << "\n";
  tr1.in(pos, now);
}

inline void solve(int pos, int pre) {
  tag += abs(pos - pre);
  int l = tr2.q(1, pos), r = tr1.q(pos, n);
  l -= (n - (pos - 1)); r -= pos;
  // cout << l << " " << r << "\n";
  int now = min(l, r);
  now -= abs(pos - pre);
  add1(pre, now);
  add2(pre, now);
  // for(int i = 1; i <= n; i ++)
  //   cout << tr1.q(i, i) - i + tag << " ";
  // putchar('\n');
}

main() {
  read(n); read(Q); read(x); read(y);
  tr1.init(); tr2.init();
  add1(y, 0); add2(y, 0);
  a[0] = x;
  for(int i = 1; i <= Q; i ++) read(a[i]);
  for(int i = 1; i <= Q; i ++) solve(a[i], a[i - 1]);
  ans = inf;
  for(int i = 1; i <= n; i ++) {
    res[i] = tr1.q(i, i) - i;
    ans = min(ans, res[i]);
  }
  cout << ans + tag << "\n";
}

Submission Info

Judge Result