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
#include<bits/stdc++.h>
#include "message.h"
#include "teatr.h"

#define FOR(i,a,b) for(int i=a;i<b;++i)
#define FOROP(i,a,b,op) for(int i=a;i<b;op)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define PB push_back
#define FI first
#define SE second
#define umap unordered_map
#define uset unordered_set
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int, int>
#define ALL(X) (X).begin(),(X).end()
//#ifndef DEBUG
//#define endl (char)10
//#endif
using namespace std;
using ll = long long;

// > 2 * MAX_ROWS / BLOCK_COUNT
#define MAX_N 14290000
#define BLOCK_COUNT 14
int elems[MAX_N];
int temp[MAX_N];
int instance_id;
int n;
int breakpts[BLOCK_COUNT + 1];
int seg1, seg2;

ll inversions(int b, int e){
    if (e <= b + 1) return 0;
    int s = (e + b) / 2;
    ll ans = inversions(b, s) + inversions(s, e);
    int i = b, j = s, idx = b;
    while(i < s || j < e){
        if (s == i){
            temp[idx++] = elems[j++];
        } else if (e == j){
            temp[idx++] = elems[i++];
            ans += (e - s);
        } else {
            if (elems[i] > elems[j]){
                temp[idx++] = elems[j++];
            } else {
                temp[idx++] = elems[i++];
                ans += (j - s);
            }
        }
    }
    FOR(i,b,e){
        elems[i] = temp[i];
    }
    return ans;
}

void fill_seg(){
    int idx = 0;
    FOR(i,0,BLOCK_COUNT) {
        FOR(j,i+1,BLOCK_COUNT) {
            if (idx == instance_id){
                seg1 = i;
                seg2 = j;
                return;
            }
            idx++;
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    instance_id = MyNodeId();
    int total_n = GetN();
    if (total_n < 1000000){
        if (instance_id == 0){
            FOR(i,0,total_n) elems[i] = GetElement(i);
            cout << inversions(0, total_n);
        }
        return 0;
    }
    FOR(i,0,BLOCK_COUNT){
        breakpts[i] = i * (total_n / BLOCK_COUNT);
    }
    breakpts[BLOCK_COUNT] = total_n;
    if (instance_id > 90){
        if (instance_id < 98){
            int pidx = 2 * (instance_id - 91);
            int idx = 0;
            FOR(i,breakpts[pidx],breakpts[pidx+1]) elems[idx++] = GetElement(i);
            PutLL(0, inversions(0, idx));
            pidx++;
            idx = 0;
            FOR(i,breakpts[pidx],breakpts[pidx+1]) elems[idx++] = GetElement(i);
            PutLL(0, inversions(0, idx));
            Send(0);
        }
        return 0;
    }
    fill_seg();
    int idx = 0;
    FOR(i,breakpts[seg1],breakpts[seg1 + 1]) elems[idx++] = GetElement(i);
    FOR(i,breakpts[seg2],breakpts[seg2 + 1]) elems[idx++] = GetElement(i);
    ll ans = inversions(0, idx);

    if (instance_id != 0){
        PutLL(0, ans);
        Send(0);
    } else {
        FOR(i,1,91){
           Receive(i);
           ans += GetLL(i);
        }
        FOR(i,91,98){
            Receive(i);
            ans -= 12 * GetLL(i);
            ans -= 12 * GetLL(i);
        }
        cout << ans << endl;
    }
}