Advertisement
pdpd123

wrong ordering pairs

Sep 16th, 2019
292
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int a[500010], temp[500010];
  5. void merge_sort(int, int);
  6. int ans = 0;
  7.  
  8. int main(){
  9.     int n;
  10.     cin >> n;
  11.     for(int i=0; i<n; i++) cin >> a[i];
  12.     merge_sort(0, n);
  13.     cout << ans << endl;
  14. }
  15.  
  16. void merge_sort(int l, int r){
  17.     if(l+1 == r) return;
  18.     int mid = l + r >> 1;
  19.     merge_sort(l, mid), merge_sort(mid, r);
  20.     int lptr = l, rptr = mid, ptr = l;
  21.     while(lptr < mid || rptr < r){
  22.         if(lptr != mid && (rptr == r || a[lptr] < a[rptr]))
  23.             temp[ptr++] = a[lptr++], ans += rptr - mid;
  24.         else temp[ptr++] = a[rptr++];
  25.     }
  26.     for(int i=l; i<r; i++) a[i] = temp[i];
  27. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement