Submission #2694517


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

ll d[N], df[N], kek[N];

void update(int l, int r, ll x) {
    d[l] += x;
    d[r + 1] -= x + r - l;
    ++df[l];
    --df[r];
}

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;
        }
        int l = (a[i] + 2) % m;
        int r = (a[i + 1]) % m;
        if (!l) {
            l += m;
        }
        if (!r) {
            r += m;
        }
        if (l > r) {
            update(l, m, 1);
            update(1, r, m - l + 2);
        } else {
            update(l, r, 1);
        }
    }
    ll ans = s;
    ll tmp = 0;
    for (int i = 1; i <= m; ++i) {
        tmp += df[i - 1];
        d[i] += tmp;
    }
    for (int i = 1; i <= m; ++i) {
        kek[i] = kek[i - 1] + d[i];
    }
    for (int i = 1; i <= m; ++i) {
        ans = min(ans, s - kek[i]);
    }
    cout << ans;
    return 0;
}

Submission Info

Submission Time
Task E - guruguru
User meatrow
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1461 Byte
Status AC
Exec Time 14 ms
Memory 3328 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 22
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 5 ms 1536 KB
half1.txt AC 3 ms 2176 KB
half2.txt AC 7 ms 2048 KB
half3.txt AC 10 ms 1664 KB
half4.txt AC 11 ms 2560 KB
min_m.txt AC 1 ms 256 KB
min_n.txt AC 2 ms 1792 KB
mx0.txt AC 14 ms 3328 KB
mx1.txt AC 14 ms 3328 KB
mx2.txt AC 14 ms 3328 KB
rnd0.txt AC 1 ms 640 KB
rnd1.txt AC 1 ms 384 KB
rnd2.txt AC 2 ms 640 KB
rnd3.txt AC 3 ms 640 KB
rnd4.txt AC 10 ms 896 KB
rnd5.txt AC 2 ms 256 KB
rnd6.txt AC 1 ms 256 KB
rnd7.txt AC 2 ms 896 KB
rnd8.txt AC 2 ms 512 KB
rnd9.txt AC 1 ms 384 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB