Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
777 B
3
Indexable
Never
#include<stdio.h>
int ary[10000000];
long long int ans=0,n;
void merge_sort(int *arr,int len){
	if(len<=1){
		return;
	}
	int leftLen=len/2;
	int rightLen=len-leftLen;

	int *leftArr=arr;
	int *rightArr=arr+leftLen;
	merge_sort(leftArr,leftLen);
	merge_sort(rightArr,rightLen);
	static int tmp[500000];
	int tmplen=0,l=0,r=0;

	while(l<leftLen && r<rightLen){
		if(leftArr[l]<=rightArr[r]){
			tmp[tmplen++]=leftArr[l++];
		}
		else{
			tmp[tmplen++]=rightArr[r++];
			ans+=leftLen-l;	
		}
	}

	while(l<leftLen){
		tmp[tmplen++]=leftArr[l++];
		
	}

	while(r<rightLen){
		tmp[tmplen++]=rightArr[r++];
	}
	for(int i=0;i<len;i++){
		arr[i]=tmp[i];
	}

}

int main(){
	scanf("%lld",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&ary[i]);
	}
	merge_sort(ary,n);
	printf("%lld\n",ans);
}