Submission #2694453

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll M = 1e9 + 7;
const int N = 100100;

ll s[N * 4], f[N * 4], lf[N * 4], d[N * 4], ld[N * 4];

void push(int n, int a, int b) {
    if (lf[n] || ld[n]) {
        ll sz = (b - a + 1) / 2;
        f[n * 2] += lf[n];
        f[n * 2 + 1] += lf[n] + ld[n] * sz;
        d[n * 2] += ld[n];
        d[n * 2 + 1] += ld[n];
        s[n * 2] += lf[n] * sz + ld[n] * sz * (sz - 1) / 2;
        s[n * 2 + 1] += (lf[n] + ld[n] * sz) * sz + ld[n] * sz * (sz - 1) / 2;
        lf[n * 2] += lf[n];
        lf[n * 2 + 1] += lf[n] + ld[n] * sz;
        ld[n * 2] += ld[n];
        ld[n * 2 + 1] += ld[n];
        lf[n] = ld[n] = 0;
    }
}

ll query(int l, int r, int n = 1, int a = 1, int b = N) {
    if (a > r || b < l) {
        return 0;
    }
    if (a >= l && b <= r) {
        return s[n];
    }
    push(n, a, b);
    int mid = (a + b) / 2;
    return query(l, r, n * 2, a, mid) + query(l, r, n * 2 + 1, mid + 1, b);
}

void update(int l, int r, int k = 1, int e = 1, int n = 1, int a = 1, int b = N) {
    if (a >= l && b <= r) {
        f[n] += k;
        d[n] += e;
        lf[n] += k;
        ld[n] += e;
        ll sz = b - a + 1;
        s[n] += k * sz + e * sz * (sz - 1) / 2;
        return;
    }
    push(n, a, b);
    int mid = (a + b) / 2;
    if (l <= mid) {
        update(l, min(mid, r), k, e, n * 2, a, mid);
    }
    if (r > mid) {
        update(max(mid + 1, l), r, k + e * max(mid - l + 1, 0), e, n * 2 + 1, mid + 1, b);
    }
    s[n] = s[n * 2] + s[n * 2 + 1];
}


int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i && a[i] < a[i - 1]) {
            ll t = (a[i - 1] - a[i] + m - 1) / m;
            a[i] += t * m;
        }
    }
    ll s = a[n - 1] - a[0];
    for (int i = 0; i + 1 < n; ++i) {
        if (a[i + 1] - a[i] < 2) {
            continue;
        }
        ll l = (a[i] + 2) % m;
        ll r = (a[i + 1]) % m;
        if (!l) {
            l += m;
        }
        if (!r) {
            r += m;
        }
        if (l > r) {
            update(l, m);
            update(1, r, m - l + 2);
        } else {
            update(l, r);
        }
    }
    ll ans = s;
    for (int i = 1; i <= m; ++i) {
        ans = min(ans, s - query(i, i));
    }
    cout << ans;
    return 0;
}

Submission Info

Judge Result