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
#include <bits/stdc++.h>
#include "message.h"
#include "teatr.h"
using namespace std;
typedef long long ll;


int id, NN;
int n;

int limPocz, limKon;

const int SIZE = 1e6+2;

vector<int> tab;

void init(){
    id = MyNodeId();
    NN = NumberOfNodes();
    n = GetN();

    if(id >= n)
        exit(0);

    NN = min(NN,n);
}

void setInterval(){
    limPocz = (id*(ll)n/NN);
    limKon = ((id+1)*(ll)n/NN)-1;
    limKon = min(limKon,n);
    limKon = max(limKon,0);
}

int bit[SIZE];

inline void bitAdd(int i){
    for(;i>0; i -= (i&-i))
        bit[i]++;
}

inline int bitQuery(int i){
    int res = 0;
    for(;i<SIZE; i += (i&-i))
        res += bit[i];   
    return res; 
}


int main(){
    init();
    setInterval();
    limPocz++; limKon++;

    tab.resize(SIZE);
    int x;
    for(int i=0;i<n;i++){
        x = GetElement(i);
        tab[x]++;
    }
    
    int a = -1,b = -1,cta,ctb;
    int sum = 0;
    for(int i=0;i<SIZE;i++){
        if(sum + tab[i] >= limPocz && a == -1){
            a = i;
            cta = limPocz - sum;
        }
        if(sum + tab[i] >= limKon && b == -1){
            b = i;
            ctb = limKon - sum;
        }
        sum += tab[i];
    }

    int gtThanMe = 0;
    int strictlyGtThanMe = 0;
    int ileA = 0, ileB = 0;

    long long inversions = 0;

    for(int i=0;i<n;i++){
        x = GetElement(i);

        if(x == a)
            ileA++;
        if(x == b)
            ileB++; 
        

        if((x > a || (x == a && ileA >= cta)) && (x < b || (x == b && ileB <= ctb))){
            if(x == b)
                inversions += strictlyGtThanMe;
            else
                inversions += gtThanMe + bitQuery(x+1);
        
            bitAdd(x);
        }
        else{
            if(x >= b)
                gtThanMe++;
            if(x > b)
                strictlyGtThanMe++;
        }
    }

    if(id != 0){
        PutLL(0,inversions);
        Send(0);
    }
    else{
        for(int i=1;i<NN;i++){
            Receive(i);
            inversions += GetLL(i);
        }
        cout<<inversions<<"\n";
    }

}