Submission #3008695


Source Code Expand

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

struct M {
  using T = lint;
  using U = lint;
  static void ap(T& a, const U& g) { a += g; }
  // static void ap(U& f, const U& g) { f += g; }
  static constexpr U id() { return 0; }
};

template<class M> struct ST {
  using T = typename M::T;
  using U = typename M::U;
  int n;
  V<T> t;
  V<U> u;

  ST(int n) : n(n) {
    t.resize(n, 0);
    u.assign(n, M::id());
  }

  void _ap(int i, const U& f) {
    if (i < n) M::ap(u[i], f);
    else M::ap(t[i - n], f);
  }

  T get(int i) {
    T res = t[i];
    for (i += n; i >>= 1;) M::ap(res, u[i]);
    return res;
  }

  void set(int l, int r, const U& f) {
    stack<int> s;
    for (int i = l + n; i >>= 1;) s.push(i);
    for (int i = r + n - 1; i >>= 1;) s.push(i);
    while (!s.empty()) {
      int i = s.top(); s.pop();
      _ap(2 * i, u[i]);
      _ap(2 * i + 1, u[i]);
      u[i] = M::id();
    }
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) _ap(l++, f);
      if (r & 1) _ap(--r, f);
    }
  }
};

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  lint n, m; cin >> n >> m;
  V<lint> a(n); for (int i = 0; i < n; i++) cin >> a[i];
  ST<M> st(m + 1);
  for (int i = 0; i < n - 1; i++) {
    if (a[i] < a[i + 1]) {
      st.set(a[i], a[i + 1], -1);
    } else {
      st.set(0, a[i + 1], -1);
      st.set(a[i], m, -1);
    }
    st.set(a[i + 1] - 1, a[i + 1], (a[i + 1] - a[i] + m) % m);
  }
  V<> s(m);
  for (int i = 0; i < n - 1; i++) s[0] += min((a[i + 1] - a[i] + m) % m, a[i + 1]);
  for (int i = 0; i < m - 1; i++) s[i + 1] = s[i] + st.get(i);
  cout << *min_element(s.begin(), s.end()) << '\n';
}

Submission Info

Submission Time
Task E - guruguru
User risujiroh
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2076 Byte
Status WA
Exec Time 307 ms
Memory 3072 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
AC × 18
WA × 4
Set Name Test Cases
Sample sample1.txt, sample2.txt
All half0.txt, half1.txt, half2.txt, half3.txt, half4.txt, min_m.txt, min_n.txt, mx0.txt, mx1.txt, mx2.txt, rnd0.txt, rnd1.txt, rnd2.txt, rnd3.txt, rnd4.txt, rnd5.txt, rnd6.txt, rnd7.txt, rnd8.txt, rnd9.txt, sample1.txt, sample2.txt
Case Name Status Exec Time Memory
half0.txt AC 61 ms 1664 KB
half1.txt AC 34 ms 2304 KB
half2.txt AC 107 ms 2176 KB
half3.txt AC 161 ms 1664 KB
half4.txt WA 177 ms 2560 KB
min_m.txt AC 1 ms 256 KB
min_n.txt AC 15 ms 2176 KB
mx0.txt WA 288 ms 3072 KB
mx1.txt WA 287 ms 2944 KB
mx2.txt WA 307 ms 3072 KB
rnd0.txt AC 5 ms 768 KB
rnd1.txt AC 2 ms 384 KB
rnd2.txt AC 12 ms 512 KB
rnd3.txt AC 37 ms 640 KB
rnd4.txt AC 126 ms 896 KB
rnd5.txt AC 7 ms 256 KB
rnd6.txt AC 1 ms 256 KB
rnd7.txt AC 7 ms 768 KB
rnd8.txt AC 17 ms 384 KB
rnd9.txt AC 3 ms 512 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB