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
90
91
92
93
#include "message.h"
#include "teatr.h"
//#include "bits/stdc++.h"

#include <algorithm>    
#include <iostream>
#include <map>

using namespace std;


#define INTERVAL pair<int, int>
#define MAP map<int, int>


MAP tree[1000001];


void increase_count(INTERVAL key) {
    MAP& counter = tree[key.first];
    MAP::iterator ptr = counter.find(key.second);
    if (ptr == counter.end()) counter.insert( pair<int,int>(key.second,1) );
    else                      ptr->second++;    
}


int get_count(INTERVAL key) {
    MAP& counter = tree[key.first];
    MAP::iterator ptr = counter.find(key.second);
    if (ptr == counter.end()) return 0;
    else                      return ptr->second;        
}


void insert_tree(int first, int end, int value) {
    increase_count( INTERVAL(first,end) );
    if (first+1>=end) return;

    int c = (end+first)/2;
    if (value>=c) {//right=[c, end)
        insert_tree(c, end, value);
    } else {        //left=[first, c) 
        insert_tree(first, c, value); 
    }
}

int get_num_larger(int first, int end, int value) {
    //printf("[get_num_larger] [%i,%i) %i\n", first, end, value);
    if (first>value) return get_count(INTERVAL(first,end));
    if (end<=value) return 0;
    if (first+1>=end) return 0;

    //value<=first and value<end
    int c = (end+first)/2;
    int right = get_num_larger(c, end, value);
    int left  = get_num_larger(first, c, value);
    return right+left;
}





int main() {
    int n = GetN();
    int num_nodes = NumberOfNodes();
    int hrange = 1000001;
    int my_id = MyNodeId();
    int per_node = hrange/num_nodes + 1;
    int first = my_id*per_node;
    int end   = min( (my_id+1)*per_node, hrange);
    
    long long conflicts = 0;
    for (int r=0; r<n; ++r) {
        int h = GetElement(r);
        conflicts += get_num_larger(first, end, h);
        if (h>=first and h<end) insert_tree(first, end, h);
    }

    if (my_id==0) {
        for (int n=1; n<num_nodes; ++n) {
            Receive(n);
            conflicts += GetLL(n);  
        }
        cout<<conflicts<<endl;
    } else {
        PutLL(0, conflicts);
        Send(0);
    }


    return 0;
}