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
// Karol Kosinski 2018
#include "message.h"
#include "teatr.h"
#include <cstdio>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FOD(i,b,a) for(int i=(b)-1;i>=(a);--i)
//#define DEBUG(x...) printf(x);
#define DEBUG(x...)
using namespace std;
typedef long long LL;

const int MX = 1000003;
const int VX = 5;
int Counter[VX], Aux[VX], Tab[MX];

int main()
{
    int id = MyNodeId(), nodes = NumberOfNodes(), n = GetN();
    int start = LL(id) * n / nodes;
    int finish = LL(id + 1) * n / nodes;
    int limit = finish - start;
    LL res = 0;
    
    FOR(i,start,finish) Tab[i - start] = GetElement(i);
    FOR(i,0,limit)
    {
        int x = Tab[i], sum = 0;
        ++Counter[x - 1];
        FOR(j,x,VX) sum += Counter[j];
        res += sum;
    }
    DEBUG("res = %lld\n", res);
    if(id != 0)
    {
        PutLL(0, res);
        FOR(i,0,VX) PutInt(0, Counter[i]);
        Send(0);
    }
    else
    {
        FOR(i,1,nodes)
        {
            Receive(i);
            res += GetLL(i);
            FOR(j,0,VX)
            {
                Aux[j] = GetInt(i);
                DEBUG("(%d)  Counter[%d] = %d\n", i, j, Counter[j]);
                DEBUG("(%d)  Aux[%d] = %d\n", i, j, Aux[j]);
            }
            LL part = 0;
            FOD(j,VX-1,0)
            {
                part += Counter[j + 1];
                DEBUG("(%d)  part = %lld,  Aux[%d] = %d\n",
                      i, part, j, Aux[j]);
                res += part * Aux[j];
            }
            FOR(j,0,VX) Counter[j] += Aux[j];
        }
        printf("%lld\n", res);
    }
    return 0;
}