Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int a[500010], temp[500010];
- void merge_sort(int, int);
- int ans = 0;
- int main(){
- int n;
- cin >> n;
- for(int i=0; i<n; i++) cin >> a[i];
- merge_sort(0, n);
- cout << ans << endl;
- }
- void merge_sort(int l, int r){
- if(l+1 == r) return;
- int mid = l + r >> 1;
- merge_sort(l, mid), merge_sort(mid, r);
- int lptr = l, rptr = mid, ptr = l;
- while(lptr < mid || rptr < r){
- if(lptr != mid && (rptr == r || a[lptr] < a[rptr]))
- temp[ptr++] = a[lptr++], ans += rptr - mid;
- else temp[ptr++] = a[rptr++];
- }
- for(int i=l; i<r; i++) a[i] = temp[i];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement