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
120
121
122
123
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include "teatr.h"
#include "message.h"

using namespace std;

typedef vector<int> VI;
typedef unsigned long long LL;

#define FOR(x, b, e) for (int x = b; x <= (e); ++x)
#define FORD(x, b, e) for (int x = b; x >= (e); --x)
#define REP(x, n) for (int x = 0; x < (n); ++x)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i)
#define PB push_back
#define ST first
#define ND second

const int MAX_SIZE = 1000000;

class Solver {
  public:
    int n, nodes, start, end;

    void readInput() {
        n = GetN();
        nodes = n / MAX_SIZE;
        if(n % MAX_SIZE > 0) nodes++;
        start = MyNodeId() * MAX_SIZE;
        end = min(n, start + MAX_SIZE);
    }

    LL merge(VI &a, VI &b, int left, int right) {
        int ave = left + (right - left) / 2;
        for (int i = left; i < right; i++) {
            b[i] = a[i];
        }
        int i = left;
        int j = left;
        int k = ave;
        LL result = 0;
        while (i < right) {
            if (j == ave) {
                while (i < right) {
                    a[i++] = b[k++];
                }
            }
            else if (k == right) {
                while (i < right) {
                    a[i++] = b[j++];
                }
            }
            else if (b[j] <= b[k]) {
                a[i++] = b[j++];
            }
            else {
                result += ave - j;
                a[i++] = b[k++];
            }
        }
        return result;
    }

    LL getInversions(VI &a, VI &b, int left, int right) {
        LL inversions = 0;
        if (right <= left + 1)
            return inversions;
        int ave = left + (right - left) / 2;
        inversions += getInversions(a, b, left, ave);
        inversions += getInversions(a, b, ave, right);
        inversions += merge(a, b, left, right);
        return inversions;
    }

    void solve() {
        if(MyNodeId() >= nodes) return;
        VI data(end - start);
        VI tmp(end - start);
        REP(i, data.size()) {
            data[i] = GetElement(start + i);
        }
        LL result = getInversions(data, tmp, 0, data.size());
        

        VI numbers(MAX_SIZE + 1, 0);
        for(int i = end; i < n; i++) {
            numbers[GetElement(i)]++;
        }
        for(int i = 1; i < numbers.size(); i++) {
            numbers[i] += numbers[i - 1];
        }
        REP(i, data.size()) {
            result += numbers[data[i] - 1];
        }
        if(MyNodeId() < nodes - 1) {
            PutLL(nodes - 1, result);
            Send(nodes - 1);
        } else {
            for(int i = nodes - 2; i >= 0; i--) {
                Receive(i);
                result += GetLL(i);
            }
            cout << result << '\n';
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    Solver solver;
    solver.readInput();
    solver.solve();
    return 0;
}