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
//Aleksander Łukasiewicz
#include<bits/stdc++.h>
#include "message.h"
#include "teatr.h"
using namespace std;

#define fru(j,n) for(int j=0; j<(n); ++j)
#define tr(it,v) for(typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define ALL(G) (G).begin(),(G).end()

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int INF = 1000000009;
const int MAXN = 1024*1024;

int N, n, myId, M;
int tab[MAXN + 3], cnt[MAXN + 3], pref[MAXN + 3];
int tree[2*MAXN + 10];
int nodes;

void Update(int a, int add){
    a += MAXN;
    while(a){
        tree[a]+=add;
        a/=2;
    }
}

int GetSum(int a, int b){
    a+=MAXN; b+=MAXN;
    int ret = 0;
    while(a<=b){
        if(a%2==1) ret += tree[a];
        if(b%2==0) ret += tree[b];
        a = (a+1)/2;
        b = (b-1)/2;
    }
    return ret;
}

int main(){
    N = GetN();
    myId = MyNodeId();
    nodes = NumberOfNodes();
    n = (N+nodes-1)/nodes;
    
    for(int i=0; i<n; i++){
        int k = myId*n + i;
        if(k >= N) break;
        tab[i] = GetElement(k);
        M = max(tab[i], M);
    }
    
    for(int i=(myId + 1)*n; i<N; i++){
        cnt[GetElement(i)]++;
    }
    
    for(int i=1; i<=MAXN; i++)
        pref[i] = pref[i-1] + cnt[i];
    
    LL ans = 0;
    for(int i=0; i<n; i++){
        if(tab[i] == 0) break;
        ans += GetSum(tab[i]+1, M);
        ans += pref[tab[i]-1];
        Update(tab[i], 1);
    }
    
    if(myId == 0){
        for(int i=1; i<nodes; i++){
            Receive(i);
            ans += GetLL(i);
        }
        
        printf("%lld\n", ans);
    }
    else{
        PutLL(0, ans);
        Send(0);
    }
    
return 0;
}