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

using namespace std;

const int M = 10;

const int MAX_N = 1000000, BASE = 1048576;

int n, nodes, id;
int cnt[MAX_N + 5], tree[2 * BASE + 5], cnt2[MAX_N + 5];

void insert(int pos) {
    pos += BASE;
    while (pos >= 1) {
        tree[pos]++;
        pos /= 2;
    }
}

int query(int posa) {
    posa += BASE;
    int ret = tree[posa];
    while (posa >= 1) {
        if (posa % 2 == 0) {
            ret += tree[posa + 1];
        }
        posa /= 2;
    }
    return ret;
}

int main() {
    
    n = GetN();
    nodes = NumberOfNodes();
    id = MyNodeId();
    
    int blocks = M;
    int from = (long long)(id % M) * n / blocks ;
    int to = min((long long)n, (long long)((id % M) + 1) * n / blocks);
    
    int myFrom = (long long)(id / M) * from / (nodes / blocks);
    int myTo = min((long long)from, (long long)(id / M + 1) * from / (nodes / blocks));
    for (int i = myFrom; i < myTo; ++i) {
        ++cnt[GetElement(i)];
    }
    
    for (int i = MAX_N - 1; i >= 1; i--) {
        cnt[i] += cnt[i + 1];
    }
    
    long long ans = 0;
    int myId = id / M;
    int insideFrom = from + (long long)myId * (to - from) / (nodes / blocks);
    int insideTo = min((long long)to, from + (long long)(myId + 1) * (to - from) / (nodes / blocks));
    for (int i = from; i < insideFrom; i++) {
        int x = GetElement(i);
        ans += cnt[x + 1];
        cnt2[x]++;
    }
    for (int i = MAX_N - 1; i >= 1; i--) {
        cnt2[i] += cnt2[i + 1];
    }
    for (int i = insideFrom; i < insideTo; i++) {
        int x = GetElement(i);
        insert(x);
        ans += query(x + 1);
        ans += cnt[x + 1] + cnt2[x + 1];
    }
    for (int i = insideTo; i < to; i++) {
        int x = GetElement(i);
        ans += cnt[x + 1];
    }
    
    if (id > 0) {
        PutLL(0, ans);
        Send(0);
    } else {
        for (int i = 1; i < nodes; i++) {
            Receive(i);
            ans += GetLL(i);
        }
        printf("%lld\n", ans);
    }
    return 0;
}