Submission #1397892

---

Source Code Expand

#include <iostream>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
#define INF 100000000000000000LL
using namespace std;
typedef long long ll;

int N, M, A[100010];
ll s[100010], p[100010], q[100010];

int main(void) {
  cin >> N >> M;
  REP(i, 0, N) cin >> A[i], A[i]--;

  s[0] = 0;
  REP(i, 0, N - 1) {
    if(A[i] > A[i + 1] && A[i] != 0) s[0] += A[i + 1] + 1;
    else s[0] += (A[i + 1] - A[i] + M) % M;
  }

  REP(i, 0, N) p[i] = 0;
  REP(i, 0, N - 1) p[A[i + 1]] += (A[i + 1] - A[i] - 1 + M) % M;

  REP(i, 0, M) q[i] = 0;
  REP(i, 0, N - 1) {
    if(A[i] < A[i + 1]) {
      q[A[i] + 1]++;
      q[A[i + 1]]--;
    } else {
      q[A[i] + 1]++;
      q[M]--;
      q[0]++;
      q[A[i + 1]]--;
    }
  }
  REP(i, 0, M) q[i + 1] += q[i];

  REP(i, 0, M - 1) s[i + 1] = s[i] + p[i] - q[i];

  ll ans = INF;
  REP(i, 0, M) ans = min(ans, s[i]);
  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result