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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <vector>
#include "teatr.h"
#include <cmath>
#include "message.h"

using namespace std;
using ll = long long;

const int MAXN = 1e6 + 5;

int cnt[MAXN], Tree[(1 << 20)], Base = (1 << 20);

int f(int x)
{
    return x & (-x);
}

void chTree(int node, int v)
{
    while (node <= Base)
    {
        Tree[node] += v;
        node += f(node);
    }
}

int read(int node)
{
    if (node < 0) return 0;
    int res = 0;
    while (node)
    {
        res += Tree[node];
        node -= f(node);
    }
    return res;
}

ll solve(vector<int> &V) {
    ll res = 0;
    int n = V.size();
    for (int i = 0; i < n; i++) {
        res += (i - read(V[i]));
        chTree(V[i], 1);
    }
    return res;
}

ll brute(int n) {
    vector<int> V;
    for (int i = 0; i < n; i++) {
        V.push_back(GetElement(i));
    }
    return solve(V);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n = GetN();
    int id = MyNodeId();
    int ile = NumberOfNodes();
    ile =  min(ile, n);
    if (id >= ile) {
        return 0;
    }

    if (n <= 100000) {
        if (id > 0) {
            return 0;
        }

        cout << brute(n);
        return 0;
    }

    int m = (n + ile - 1) / ile;
    int a = id * m;
    int b = min(n - 1, (id + 1) * m - 1);
    for (int i = 0; i < a; i++) {
        cnt[GetElement(i)]++;
    }
    for (int i = 1; i < MAXN; i++) {
        cnt[i] += cnt[i - 1];
    }

    ll res = 0;
    vector<int> V;
    for (int i = a; i <= b; i++) {
        int v = GetElement(i);
        V.push_back(v);
        res += (a - cnt[v]);
    }
    res += solve(V);

    //cout << res << "\n";
    if (id) {
        PutLL(0, res);
        Send(0);
        return 0;
    }

    for (int i = 1; i < ile; i++) {
        Receive(i);
        res += GetLL(i);
    }

    cout << res << "\n";
}