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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
#include "message.h"
#include "teatr.h"

using namespace std;

const int M = 102;
int ifroms[M];
int itos[M];
int vfroms[M];
int vtos[M];
int cells[M];

const int N = 1000005;
int t[N];
int tot;

int sum(int r) {
    int result = 0;
    for (; r >= 0; r = (r & (r+1)) - 1) {
        result += t[r];
    }
    return result;
}

void inc(int i, int delta) {
    tot += delta;
    for (; i < N; i = (i | (i+1))) {
        t[i] += delta;
    }
}

void wipe() {
    tot = 0;
    memset(t, 0, sizeof(t));
}

int cnt[N];
int field[M][M];

int main() {
    int nodes = NumberOfNodes();
    int myNode = MyNodeId();

    int n = GetN();
    int imx = n;
    int vmx = 1000002;
    int isz = (n + nodes - 1) / nodes;
    int vsz = (vmx + nodes - 1) / nodes;

    for (int node = 0; node < nodes; node++) {
        vfroms[node] = node * vsz;
        ifroms[node] = node * isz;
        vtos[node] = min(vmx, vfroms[node] + vsz);
        itos[node] = min(imx, ifroms[node] + isz);
    }

    int ifrom = ifroms[myNode];
    int vfrom = vfroms[myNode];
    int ito = itos[myNode];
    int vto = vtos[myNode];
    long long res = 0;

    wipe();
    for (int node = 0; node < nodes; node++) {
        int l = ifroms[node];
        int r = itos[node];
        int cell = 0;
        for (int i = l; i < r; i++) {
            int x = GetElement(i);
            if (x < vfrom) continue;
            if (x >= vto) continue;
            cnt[x]++;
            cell++;
        }
        cells[node] = cell;
        for (int v = vfrom; v < vto; v++) {
            res += 1LL * cnt[v] * (tot - sum(v));
        }
        for (int v = vfrom; v < vto; v++) {
            inc(v, cnt[v]);
            cnt[v] = 0;
        }
    }

    for (int node = 0; node < nodes; node++) {
        PutInt(0, cells[node]);
    }
    Send(0);
    // cout << myNode << " " << ifrom << " " << ito << " " << vfrom << " " << vto << " " << res << endl;

    wipe();
    for (int i = ifrom; i < ito; i++) {
        int x = GetElement(i);
        res += tot - sum(x);
        inc(x, 1);
    }

    PutLL(0, res);
    Send(0);

    if (myNode == 0) {
        long long ans = 0;
        for (int node = 0; node < nodes; node++) {
            Receive(node);
            for (int q = 0; q < nodes; q++) {
                field[node][q] = GetInt(node);
            }
        }
        for (int i1 = 0; i1 < nodes; i1++) {
            for (int j1 = 0; j1 < nodes; j1++) {
                int f1 = field[i1][j1];
                for (int i2 = i1 - 1; i2 >= 0; i2--) {
                    for (int j2 = j1 + 1; j2 < nodes; j2++) {
                        ans += 1LL * f1 * field[i2][j2];
                    }
                }
            }
        }
        for (int node = 0; node < nodes; node++) {
            Receive(node);
            ans += GetLL(node);
        }
        cout << ans << endl;
    }
    return 0;
}