Untitled
unknown
c_cpp
3 years ago
777 B
6
Indexable
#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); }
Editor is loading...