Submission #8908647


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define f first
#define s second
#define MAXN 100010

priority_queue<pi,vpi,greater<pi>> pq;
vi V[MAXN];
ll N,M;
ll W,ans;
ll A[MAXN];
ll save;

int main(){
	cin>>N>>M;
	for (ll i=1;i<=N;++i){
		cin>>A[i];
	}
	for (ll i=1;i<N;++i){
		ll w = (A[i+1]+M-A[i])%M;
		W += w;
		if (A[i+1] < A[i]){
			save += (M-A[i]);
			pq.push(mp(A[i+1], A[i]));
			// cout<<"Push "<<A[i]<<' '<<A[i+1]<<'\n';
		}
		V[A[i]].pb(A[i+1]);
	}
	ll sv = 0;
	// cout<<"Save 1 "<<W-save<<'\n';
	sv = max(sv,save);
	for (ll i=2;i<=M;++i){
		// cout<<pq.top().f<<'\n';
		while(SZ(pq) && pq.top().f == i-1){
			pi p = pq.top();pq.pop();
			// cout<<"Remove "<<p.s<<' '<<p.f<<'\n';
			save -= (p.f+M-p.s)%M; 
			++save;
		}
		save += SZ(pq);
		for (auto x:V[i-1]){
			if(i-1>x)pq.push(mp(x+M,i-1));
			else pq.push(mp(x,i-1));
			// cout<<i-1<<' '<<x<<'\n';
		}
		// cout<<"Save "<<i<<' '<<W-save<<'\n';
		sv = max(sv,save);
	}
	cout<<W-sv<<'\n';
}

Submission Info

Submission Time
Task E - guruguru
User dvdg6566
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1290 Byte
Status AC
Exec Time 50 ms
Memory 7284 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 13 ms 3328 KB
half1.txt AC 6 ms 2816 KB
half2.txt AC 23 ms 3964 KB
half3.txt AC 35 ms 4600 KB
half4.txt AC 38 ms 5240 KB
min_m.txt AC 2 ms 2560 KB
min_n.txt AC 3 ms 2560 KB
mx0.txt AC 49 ms 7284 KB
mx1.txt AC 49 ms 7284 KB
mx2.txt AC 50 ms 7284 KB
rnd0.txt AC 2 ms 2560 KB
rnd1.txt AC 2 ms 2560 KB
rnd2.txt AC 4 ms 2816 KB
rnd3.txt AC 10 ms 3328 KB
rnd4.txt AC 35 ms 4984 KB
rnd5.txt AC 3 ms 2688 KB
rnd6.txt AC 2 ms 2560 KB
rnd7.txt AC 3 ms 2688 KB
rnd8.txt AC 6 ms 2816 KB
rnd9.txt AC 2 ms 2560 KB
sample1.txt AC 2 ms 2560 KB
sample2.txt AC 2 ms 2560 KB