View difference between Paste ID: ujzDZs7U and wBfX9vTL

-#include <bits/stdc++.h>
+#define task "LCD"
-#define X first
+
-#define Y second
+#include <iostream>
 #include <cstdio>
 
-typedef long long ll;
+
-typedef pair<int, int> pii;
+
-const int N = 3e5 + 7;
+using ll = long long;
-pair<ll, ll> bit[N];
+using ld = long double;
-int n, l, r, b[N], m;
+
-pii a[N];
+constexpr int N = 1e6 + 5;
-ll sum , res = LLONG_MAX, f[N];
+constexpr ll Inf = 1e17;
-void upd(int p, ll x, ll y, int n)
+int n, m;
 int a[N];
-    while (p<=n)
+ll b[N * 2];
 
-        bit[p].X+=x;
+void Read()
-        bit[p].Y+=y;
+
-        p+=(p&(-p));
+    cin >> n >> m;
     for (int i = 1; i <= n; ++i)
     {
-pair<ll, ll> Get(int p)
+        cin >> a[i];
         --a[i]; /// Change 1, 2, ..., m -> 0, 1, 2, ..., (m - 1)
-    ll res = 0, dem = 0;
+
-    while (p>0)
+
 
-        res+=bit[p].X;
+void Solve()
-        dem+=bit[p].Y;
+
-        p-=(p&(-p));
+    ll sum(0); // Answer without X
 
-    return make_pair(res,dem);
+    for (int i = 1; i < n; ++i)
     {
-int main()
+        if (a[i] > a[i + 1])
             a[i + 1] += m;
-
+
-    ios_base::sync_with_stdio(0);
+        sum += a[i + 1] - a[i];
 
         b[a[i] + 2] += 1;
-    cin>>n>>m;
+        b[a[i + 1] + 1] += -1 - (a[i + 1] - a[i] - 1);
-    for (int i=1; i<=n; i++) cin>>b[i];
+        b[a[i + 1] + 2] += (a[i + 1] - a[i] - 1);
-    for (int i=1; i<n; i++)
+
-        if (b[i]<b[i+1]) a[i] = make_pair(b[i],b[i+1]); else a[i] = make_pair(b[i],b[i+1] + m);
+        if (a[i + 1] >= m)
-    n--;
+            a[i + 1] -= m;
-    sort(a+1,  a + 1  + n);
+
-    for (int i=1; i<=n; i++) sum = sum + a[i].Y - a[i].X;
+
-    int j = 0;
+    for (int i = 1; i < m * 2; ++i)
-    for (int x = 1; x<=m; x++)
+        b[i] += b[i - 1];
 
-        while (j<n && a[j+1].X<x)
+    for (int i = 1; i < m * 2; ++i)
-        {
+        b[i] += b[i - 1];
-            j++;
+
-            upd(a[j].Y, a[j].X, 1, 2*m);
+    ll ans(Inf);
-        }
+
-        pair<ll, ll> t = Get(2*m), q = Get(x-1);
+    for (int i = 0; i < m; ++i)
-        ll cnt = t.Y - q.Y;
+        ans = min(ans, sum - b[i] - b[i + m]);
-        ll sum1 = t.X- q.X;
+
-        ll tmp = sum + sum1 - 1LL*cnt*x + cnt;
+    cout << ans;
-        f[x] = tmp;
+
 
-    for (int i=1; i<=2*m; i++) bit[i] = make_pair(0,0);
+int32_t main()
-    j = 0;
+
-    for (int x = 1; x<=m; x++)
+    ios::sync_with_stdio(0);
     cin.tie(0);
-        while (j<n && a[j+1].X<x+m)
+
-        {
+    if (fopen(task ".INP", "r"))
-            j++;
+
-            upd(a[j].Y, a[j].X, 1, 2*m);
+        freopen(task ".INP", "r", stdin);
-        }
+        freopen(task ".OUT", "w", stdout);
-        pair<ll, ll> t = Get(2*m), q = Get(x+m-1);
+
-        ll cnt = t.Y - q.Y;
+    Read();
-        ll sum1 = t.X- q.X;
+    Solve();
-        ll tmp = f[x] + sum1 - 1LL*cnt*(x+m) + cnt;
+
-        f[x] = tmp;
+
-        res = min(res,f[x]);
+/*
 4 5
-    cout<<res;
+1 2 4 5
-    return 0;
+*/