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
#include <iostream>
#include <set>
#include "teatr.h"
#include "message.h"
using namespace std;

long long merge(int arr[], int l, int m, int r) { 
    long long sum = 0;
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    int L[n1], R[n2]; 
  
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
  
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i++];
        }
        else { 
            arr[k] = R[j++];
            sum += n1 - i;
        } 
        k++; 
    } 
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    return sum;
} 

long long mergeSort(int arr[], int l, int r) { 
    long long sum = 0;
    if (l < r) { 
        int m = l+(r-l)/2;
        sum += mergeSort(arr, l, m);
        sum += mergeSort(arr, m+1, r); 

        sum += merge(arr, l, m, r);
    }
    return sum;
} 

int main() {
    int n = GetN();
    int id = MyNodeId();
    int l = id * 1000000;
    int r = (id + 1) * 1000000;
    int countl[1000002];
    int arr[1000002];
    int nodes = n / 1000000;
    int e, s;
    long long sum = 0;
    s = min(r, n) - l;
    for (int i = l; i < min(r, n); ++i) {
        e = GetElement(i);
        ++countl[e];
        arr[i - l] = e;
    }
    sum += mergeSort(arr, 0, s - 1);
    for (int i = 0; i < 1000000; ++i) {
        arr[i] = 0;
    }
    for (int i = r; i < n; ++i) {
        e = GetElement(i);
        ++arr[e];
    }
    for (int i = 1000000; i >= 0; --i) {
        countl[i] += countl[i + 1];
    }
    for (int i = 0; i <= 1000000; ++i) {
        sum += (long long)((long long)arr[i] * (long long)countl[i + 1]);
    }
    if (id != 0) {
        PutLL(0, sum);
    }
    else {
        for (int i = 0; i < nodes; ++i) {
            int q = Receive(-1);
            sum += GetLL(q);
        }
        cout<<sum<<endl;
    }
}