Submission #1394943

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, int(n) + 1)
#define rrep(i, n) RFOR(i, 0, n)
#define rrep1(i, n) RFOR(i, 1, int(n) + 1)
#define all(c) begin(c), end(c)
const int MOD = 1000000007;

template <typename T>
void __dump__(std::ostream &os, const T &first) {
    os << first;
}
template <typename First, typename... Rest>
void __dump__(std::ostream &os, const First &first, const Rest &... rest) {
    os << first << ", ";
    __dump__(os, rest...);
}
#define dump(...)                                         \
    do {                                                  \
        std::ostringstream os;                            \
        os << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; \
        __dump__(os, __VA_ARGS__);                        \
        std::cerr << os.str() << std::endl;               \
    } while (0)

int n, m;

int reduce[200010];
int imos0[200010], imos1[200010];
// f[l] += x, f[l+1] += x+y, f[l+2] += x+2y...
void add(int l, int r, long long a, long long b) {
    imos0[l] += a;
    imos0[r] -= a;

    imos0[l] -= b * l;
    imos0[r] += b * l;

    imos1[l] += b;
    imos1[r] -= b;
}

int ss[100010];

signed main() {
    while (cin >> n >> m) {
        memset(imos0, 0, sizeof imos0);
        memset(imos1, 0, sizeof imos1);
        rep(i, n) {
            cin >> ss[i];
            --ss[i];
        }
        rep(i, n - 1) {
            int s = ss[i], d = ss[i + 1];
            dump(s, d);
            if (s < d) {
                add(s + 2, d + 1, 1, 1);
            } else if (d < s) {
                add(s + 2, s + m + 2, 1, 1);
                add(0, d + 1, m - s - 1, 1);
            }
        }

        rep(i, m) {
            imos0[i + 1] += imos0[i];
            imos1[i + 1] += imos1[i];
        }
        rep(i, m) {
            reduce[i] = imos0[i] + imos1[i] * i;
            // dump(i, reduce[i]);
        }

        int maxi = *max_element(reduce, reduce + m);
        int org = 0;
        rep(i, n - 1) {
            int s = ss[i], d = ss[i + 1];
            int add;
            if (s < d) add = d - s;
            else add = d + m - s;
            // dump(org);
            org += add;
        }
        dump(org, maxi);
        cout << org - maxi << endl;
    }
}

Submission Info

Judge Result