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 |
|
|
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 |