Submission #3008594

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int n,m;
ll A[100010] = {0},B[100010] = {0};

int main(){
	cin >> n >> m;
	ll sum = 0;
	vector<P> v(n);
	for(int i=0;i<n;i++){
		cin >> A[i];
		B[i] = A[i];
		if(i>=1){
			if(B[i-1]>A[i]) A[i] += m;
			sum += A[i]-B[i-1];
			v[i-1] = {B[i-1],A[i]};
//			cout << v[i-1].first << " " << v[i-1].second << endl;
		}
	}
	sort(v.begin(),v.end());
	P F[2*(m+2)];
//	cout << endl;
	for(int i=0;i<2*(m+2);i++){
		F[i] = {0,0};
	}
	for(int i=0;i<n;i++){
		F[v[i].first+1].second++;
		F[v[i].second+1].second--;
		F[v[i].second+1].first -= v[i].second-v[i].first;
	}
	ll ans = 0;
	for(int i=2;i<2*(m+2);i++){
//		cout << F[i].first << " " << F[i].second << " ";
		F[i].second += F[i-1].second;
		F[i].first += F[i].second + F[i-1].first;
//		cout << F[i].first << " " << F[i].second << endl;
	}
	for(int i=1;i<=m;i++){
		ans = max(ans,F[i].first+F[i+m].first-F[i].second-F[i+m].second);
	}
//	cout << sum << endl;
	cout << sum - ans << endl;
}

Submission Info

Judge Result