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
124
125
126
127
128
129
#include <iostream>
#include <math.h>

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

#define LL long long
#define MIN_N 1000
#define MAX_SIZE 1000010
#define MAX_LENGTH 100000000

using namespace std;


LL merge(int *values, int start, int mid, int end) {
    LL count = 0;
    int first[mid-start+2], second[end-mid+1], i, j, L;
    j = 0;
    for (i = start; i < mid+1; i++)
        first[j++] = values[i];
    first[j] = MAX_SIZE;
    L = j + 1;
    j = 0;
    for (i = mid + 1; i < end+1; i++)
        second[j++] = values[i];
    second[j] = MAX_SIZE;
    i = 0, j = 0;
    for (int k = start; k < end+1; k++) {
        if (first[i] <= second[j])
            values[k] = first[i++];
        else {
            values[k] = second[j++];
            count += L - i - 1;
        }
    }
    return count;
}

LL mergesort(int *values, int start, int end) {
    LL count = 0;
    int mid;
    if (start < end) {
        mid = (start + end) / 2;
        count += mergesort(values, start, mid);
        count += mergesort(values, mid + 1, end);
        count += merge(values, start, mid, end);
    }
    return count;
}

int main()
{
    int nodes, node_id, N, n, v, k, i;
    int values[MAX_SIZE];
    int left[MAX_SIZE], max_v;
    int k_start, k_stop, eff_node_id, next_node_id = 1, conn_node_id;
    LL count = 0, right_count;
    nodes = NumberOfNodes();
    node_id = MyNodeId();

    N = GetN();

    n = max(N / nodes + 1, MIN_N);

    k_start = n * node_id;
    k_stop = min(n * (node_id + 1), N);

    if (k_start < k_stop) {
        i = -1;
        for (k = k_start; k < k_stop; k++){
            values[++i] = GetElement(k);
        }
        count = mergesort(values, 0, i);
    } else
        return 0;

    eff_node_id = node_id;


    while (true) {
        if (eff_node_id % 2 == 0) {
            conn_node_id = node_id + next_node_id;
            if (n * conn_node_id < N) {
                Receive(conn_node_id);
                right_count = GetLL(conn_node_id);
            } else if (node_id > 0) {
                eff_node_id /= 2;
                next_node_id *= 2;
                continue;
            } else
                break;
            count += right_count;
            for (k = 0; k < MAX_SIZE; k++)
                left[k] = 0;
            k_start = n * node_id;
            k_stop = n * conn_node_id;
            max_v = 0;
            for (k = k_start; k < k_stop; k++) {
                v = GetElement(k);
                left[v]++;
                if (v > max_v) max_v = v;
            }
            for (k = max_v; k > 0; k--){
                left[k-1] += left[k];
            }
            k_start = n * conn_node_id;
            k_stop = min(n * (conn_node_id + next_node_id), N);

            for (k = k_start; k < k_stop; k++) {
                v = GetElement(k);
                if (v < max_v) {
                    count += left[v+1];
                }
            }
        } else {
            // send value
            conn_node_id = node_id - next_node_id;
            PutLL(conn_node_id, count);
            Send(conn_node_id);
            return 0;
        }
        eff_node_id /= 2;
        next_node_id *= 2;
    }

    cout << count << endl;
    return 0;
}