1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include "teatr.h"
#include "message.h"

using namespace std;

int *A;

long long mergeInversions(int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = new int[n1 + 2];
    int *R = new int[n2 + 2];
    for (int i = 1; i <= n1; i++) {
        L[i] = A[p + i - 1];
    }
    for (int j = 1; j <= n2; j++) {
        R[j] = A[q + j];
    }
    L[n1 + 1] = R[n2 + 1] = 2000000000;
    int i = 1, j = 1;
    long long inversions = 0;
    for (int k = p; k <= r; k++) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
            inversions += n1 - i + 1;
        }
    }
    delete[] L;
    delete[] R;
    return inversions;
}

long long countInversions(int p, int r) {
    long long inversions = 0;
    if (p < r) {
        int q = (p + r) / 2;
        inversions += countInversions(p, q);
        inversions += countInversions(q + 1, r);
        inversions += mergeInversions(p, q, r);
    }
    return inversions;
}

int main() {
    int n = GetN();
    A = new int[n];
    int id = MyNodeId();
    if (id == 0) {
        for (int k = 0; k < n; k++) {
            A[k + 1] = GetElement(k);
        }
        printf("%lld\n", countInversions(1, n));
    }

    return 0;
}