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

using namespace std;

int segment[1000007];
int before[1000007];
int pref[1000007];
int tmp[1000007];


long long count_on_segment(int p, int k)
{
    if (k - p <= 1)
        return 0;
    long long inv = 0;
    int m = p + (k-p)/2;
    inv += count_on_segment(p, m);
    inv += count_on_segment(m, k);
    int l1 = p, l2 = m;
    //cout << p <<" "<< k<< " "<< m<<endl;
    while (l1 < m && l2 < k)
    {
        if (segment[l1] <= segment[l2])
        {
            tmp[l1 + l2 - m] = segment[l1];
            l1++;
        }
        else
        {
            tmp[l1 + l2 - m] = segment[l2];
            l2++;
            inv += (m-l1);
            //cout << "||"<< l1<< " "<<p<< " "<< inv <<endl;
        }
    }
    while (l1 < m)
    {
        tmp[l2 + l1 - m] = segment[l1];
        l1++;
    }
    while (l2 < k)
    {
        tmp[l2 + l1 - m] = segment[l2];
        l2++;
    }
    for (int i = p; i < k; i++)
        segment[i] = tmp[i];
    //cout << p <<" "<< k<< " "<< inv<<endl;
    return inv;

}

int main()
{
    int maks;
    maks = GetN();
    int instancja = MyNodeId();
    //cout << instancja<<endl;
    int segment_length = (maks + 99)/100;
    long long inversions = 0;
    if (instancja != 0)
    {
        Receive(instancja-1);
        inversions = GetLL(instancja-1);
        //cout << " * "<<inversions << endl;
    }
	//cout << segment_length<<endl;
    int maks_num = 0;
    for (int i = 0; i < min(maks, segment_length*instancja); i++)
    {
        int num = GetElement(i);
        before[num]++;
        maks_num = max(maks_num, num);
    }
    for (int i = maks_num; i >= 0; i--)
        pref[i] = pref[i+1] + before[i];
    int start = segment_length*instancja;
    for (int i = start; i < min(maks, segment_length*(instancja+1)); i++)
        segment[i-start] = GetElement(i);
    for (int i = start; i < min(maks, segment_length*(instancja+1)); i++)
        inversions += pref[segment[i-start]+1];
    //cout << " :::" <<inversions <<endl;
    inversions += count_on_segment(0, min(maks, segment_length*(instancja+1))-start);
    if (instancja < 99)
    {
        PutLL (instancja+1, inversions);
        Send(instancja+1);
    }
    else
        cout << inversions;
}