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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// again - 100% lame approach...
// not distributed, just copy from:
// C++ program to count inversions using Binary Indexed Tree
// https://www.geeksforgeeks.org/count-inversions-array-set-3-using-bit/
// actually it looks like single instance can read all the data - isn't that too easy?

#include "message.h"
#include "teatr.h"
#include <bits/stdc++.h>

using namespace std;

/*
//compiles, so go :)
vector<int> DATA = {5, 2, 4, 4, 3};
int GetElement(int i) {
    return DATA[i % DATA.size()];
}
int GetN() {
    return DATA.size();
}
int MyNodeId() {return 0;}
int NumberOfNodes() {return 1;}
long long GetLL(int source) {return 0;}
int GetInt(int source) {return 0;}
int Receive(int source) {return 0;}
void Send(int target) {}
void PutInt(int target, int value) {}
void PutLL(int target, long long value) {}
/*
*/

typedef vector<uint64_t> BITree_t;

uint64_t getSum(BITree_t& BITree, int index) {
    uint64_t sum = 0;
    while (index > 0) {
        sum += BITree[index];
        index -= index & (-index);
    }
    return sum;
}

void updateBIT(BITree_t& BITree, int index, int val) {
    while (index < BITree.size()) {
        BITree[index] += val;
        index += index & (-index);
    }
}

int main() {
    int n = GetN();
    int histSize = 1000010;
    int nodeId = MyNodeId();
    int instances = NumberOfNodes();

    int i0 = n * (nodeId) / instances;
    int i1 = n * (nodeId + 1) / instances;

    vector<int> hist(histSize);
    for (int i = i1; i < n; i++) {
        hist[GetElement(i)]++;
    }

    //calculate partial result
    BITree_t BIT(histSize + 1);
    for (int elem = 1; elem < hist.size(); elem++) {
        if (hist[elem] > 0)
            updateBIT(BIT, elem, hist[elem]);
    }

    uint64_t invcount = 0;
    for (int i = i1 - 1; i >= i0; i--) {
        int elem = GetElement(i);
        invcount += getSum(BIT, elem - 1);
        updateBIT(BIT, elem, 1);
    }

    if (nodeId != 0) {
        PutLL(0, invcount);
        Send(0);
    } else {
        for (int k = 1; k < instances; k++) {
            Receive(k);
            invcount += GetLL(k);
        }
        cout << invcount << "\n";
    }
}