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

const int MAX_K = 1e6;
const int base = 1<<20;
int tree[2*base+5];
int z[MAX_K+3];
int suf[MAX_K+3];
int max = -1;

inline void insert(int v){
    v += base;
    tree[v]++;
    v /= 2;
    while (v > 0){
        tree[v] = tree[v*2] + tree[v*2+1];
        v /= 2;
    }
}

inline ll query(int L, int R){
    if (L > R)
        return 0;
    L += base;
    R += base;
    ll res = tree[L];
    if (L != R)
        res += tree[R];
    while (L/2 != R/2){
        if (L % 2 == 0)
            res += tree[L+1];
        if (R % 2 == 1)
            res += tree[R-1];
        L /= 2;
        R /= 2;
    }
    return res;
}

ll countInv(int L, int R){
    int x;
    ll res = 0;
    for (int i = L; i < R; i++){
        x = GetElement(i);
        res += query(x+1, max);
        max = std::max(max, x);
        insert(x);
    }
    return res;
}

void prepareSums(int L, int R){
    int x;
    for (int i = L; i < R; i++){
        x = GetElement(i);
        z[x]++;
    }
    suf[max+1] = 0;
    for (int i = max; i >= 1; i--)
        suf[i] = suf[i+1] + z[i];
}

int main(){
    int n = GetN();
    ll myId = MyNodeId();
    ll cntNodes = NumberOfNodes();

    ll step = n/cntNodes;
    if (step < 2)
        step = 2;
    cntNodes = n/step;
    if (myId >= cntNodes) return 0;

    // team-work
    int L = myId * step;
    int R = (myId+1) * step;
    if (myId == cntNodes-1)
        R = n;

    // licze liczbe inwersji na przedziale [L, R)
    ll res = countInv(L, R);

    // licze pref-sumy
    prepareSums(L, R);

    // licze takie inwersje, że lewy element (wiekszy) znajduje sie w [L, R), z prawy w pozostalej czesci ciagu
    int x;
    for (int i = R; i < n; i++){
        x = GetElement(i);
        res += suf[x+1];
    }

    // zbieranie info
    if (myId != 0){
        PutLL(0, res);
        Send(0);
        return 0;
    }
    else{
        for (int i = cntNodes-1; i >= 1; i--){
            Receive(i);
            ll tres = GetLL(i);
            res += tres;
        }
    }
    std::cout << res << "\n";
}