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
// Jedna instancja wypisuje maksymalny wzrost.

#include "message.h"
#include "teatr.h"
#include "bits/stdc++.h"

using namespace std;

#define MAX 1048576
//#define MAX 8
#define D(x)

int tree[2*MAX+10];
long long result = 0;

int insert(int x) {
    int v=x+MAX,r = 0;
    tree[v]++;
    while(v>1) {
        if(!(v%2)) r+=tree[v+1];
        v/=2;
        tree[v]++;
    }
    return r;
}

void print_tree()
{
    int v = 1,li=0;
    for(int i=1;i<2*MAX;i++) {
        cout << tree[i];
        for(int j =0; j< 2*MAX/v;j++) cout << " ";
        if(i == v+li) {
            cout << "\n";
            for(int j =0; j< MAX/v;j++) cout << " ";
            v*=2;
            li=i;
        }
    }
    cout << "\n";
}

int main() {
    int we = NumberOfNodes();
    int me = MyNodeId();
    int n = GetN();
    int blok = (n+we-1)/we;
    int a = min(blok*me,n);
    int b = min(blok*(me+1),n);
    D(cout << " a:" << a << " b:" << b << "\n");
    for(int i=0;i<a;i++) tree[GetElement(i)+MAX]++;
    for(int i=MAX-1;i>0;i--) tree[i]=tree[2*i]+tree[2*i+1];

    for(int i=a;i<b;i++) {
        int r=insert(GetElement(i));
        D(cout << i << " r:" << r << " v:" << GetElement(i) << "\n");
        D(print_tree());
        result += r;
    }

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