abc_d 玄关求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,m,c,len,a[N],d[N],ans;
map<int,bool> mp;
vector<int> v;
signed main(){
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(!mp[a[i]]){
			v.push_back(a[i]);
			mp[a[i]]=1;
		}
	}
	len=v.size();
	sort(v.begin(),v.end());
	for(int i=1;i<=n;i++){
		int x=upper_bound(v.begin(),v.end(),a[i])-v.begin()-1;
		d[x]++;
	}
	for(int i=1;i<len;i++){
		d[i]+=d[i-1];
	}
	int now=-1;
	for(int i=0;i<len;i++){
		if(d[len-1]-d[i]>=c){
			int l=i+1,r=len-1,sum=0;
			while(l<=r){
				int mid=(l+r)/2;
				if(d[mid]-d[i]>=c){
					sum=d[mid]-d[i];
					r=mid-1;
				}
				else{
					l=mid+1; 
				}
			}
			int t=v[i]-now;
			ans+=t*sum;
			//cout<<t<<" "<<sum<<endl;
		}
		else{
			int x=d[len-1]-d[i];
			int l=0,r=i,sum=0;
			while(l<=r){
				int mid=(l+r)/2;
				if(d[mid]>=c-x){
					sum=x+d[mid];
					r=mid-1;
				}
				else{
					l=mid+1;
				}
			}
			int t=v[i]-now;
			ans+=t*sum;
			//cout<<t<<" "<<sum<<endl;
		}
		now=v[i];
	}
	if(now==m-1){
		cout<<ans;
		return 0;
	}
	int l=0,r=len-1,sum=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(d[mid]>=c){
			sum=d[mid];
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	int t=m-1-now;
	ans+=t*sum;
	//cout<<t<<" "<<sum<<endl;
	cout<<ans;
	return 0;
}