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
#include "teatr.h"
#include "message.h"

#include <cstdio>
#include <vector>

//#define DBG(...) fprintf(stderr, __VA_ARGS__)
#define DBG(...)

typedef int I;
typedef long long L;
typedef std::vector<I> VI;

static const I MAXN = 100000000;
static const I MAXH = 1000000;

static L run_local() {
        L ret = 0;
        I maxh = 0;

        VI counters(MAXH);

        const I n = GetN();
        for (I i=0; i<n; ++i) {
                I e = GetElement(i) - 1;
                ++counters[e];
                if (e > maxh)
                        maxh = e;
                for (I j=e+1; j<=maxh; ++j)
                        ret += counters[j];
        }
        return ret;
}

template <I C>
static L run_maxn(const I begin, const I end) {
        const I nid = MyNodeId();
        const I nodes = NumberOfNodes();

        VI prev(C);
        VI next(C);
        // liczymy swoje countery
        if (nid+1 != nodes) {
                for (I i=begin; i<end; ++i) {
                        I e = GetElement(i) - 1;
                        if (e < C)
                                ++next[e];
                }
        }
        // odbieramy od poprzedniego
        if (nid != 0) {
                Receive(nid-1);
                for (I i=0; i<C; ++i)
                        prev[i] = GetInt(nid-1);
        }
        // wysylamy do nastepnego
        if (nid+1 != nodes) {
                for (I i=0; i<C; ++i)
                        PutInt(nid+1, prev[i] + next[i]);
                Send(nid+1);
        }
        // liczymy wynik noda
        L part = 0;
        for (I i=begin; i<end; ++i) {
                I e = GetElement(i) - 1;
                if (e < C)
                        ++prev[e];
                for (I j=e+1; j<C; ++j)
                        part += prev[j];
        }
        return part;
}

int main() {
        const I nid = MyNodeId();
        const I nodes = NumberOfNodes();
        DBG("start %d/%d\n", nid, nodes);

        const I n = GetN();
        if (n < 12) {
                if (nid != 0)
                        return 0;
                printf("%llu\n", run_local());
                return 0;
        }

        // podzial na nody
        const I per_node = n < nodes ? 1 : n / nodes;
        const I begin = nid * per_node;
        const I end = (begin + per_node > n) ? begin : (nid+1==nodes ? n : begin + per_node);
        DBG("split [%d, %d>\n", begin, end);

        L part = run_maxn<5>(begin, end);
        DBG("part %lld\n", part);
        // wysyłamy wyniki
        PutLL(0, part);
        Send(0);
        if (nid == 0) {
                L ret = 0;
                for (I n=0; n<nodes; ++n) {
                        Receive(n);
                        ret += GetLL(n);
                }
                printf("%llu\n", ret);
        }
        return 0;
}