Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
1.1 kB
0
Indexable
Never
#include <iostream>
#define MAX 1000005
typedef long long ll;
using namespace std;

ll n, arr[MAX], cnt = 0, temp[MAX];

ll merge(int left, int mid, int right) {
    int cnt = 0;
    int i = left, j = mid + 1, k = left;
    while((i <= mid) && (j <= right)) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
            cnt += (mid + 1 - i);
        }
    } 
    while(i <= mid) 
        temp[k++] = arr[i++];
    while(j <= right)
        temp[k++] = arr[j++];
    for(int i = left; i<= right; i++)
        arr[i] = temp[i];
    // cout << "merge cnt = " << cnt << endl;
    return cnt;
}

ll mergeSort(int left, int right) {
    int mid = (left + right) / 2, cnt = 0;
    if(left < right) {
        cnt += mergeSort(left, mid);
        cnt += mergeSort(mid + 1, right);
        cnt += merge(left, mid, right);
    }
    return cnt;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    ll ans = mergeSort(0, n-1);
    cout << ans << endl;
}
Leave a Comment