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
#pragma region Template 
#include <bits/stdc++.h> 

using namespace std;

#define For(i, n) for (int i = 0; i < (n); i++)
#define ForD(i, n) for (int i = (n) - 1; i >= 0; i--)
#define SORT(x) sort(begin(x), end(x))
#define REP(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#if DEBUG
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string>) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
#else
#define error(...) do {} while (0)
#endif

#define _upgrade do { ios::sync_with_stdio(0); cin.tie(0); } while (0)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#pragma endregion 

// Jedna instancja wypisuje maksymalny wzrost.

#include "message.h"
#include "teatr.h"

using namespace std;

// int GetN() { return int(1e8); }
// int GetElement(int i) { return (i * 1ll * i) % int(1e6) + 1; }

const int N = 1000 * 1000 + 10;
int tree[N];

int read(int idx){
    int sum = 0;
    while (idx > 0){
        sum += tree[idx];
        idx -= (idx & -idx);
    }
    return sum;
}

const int MaxIdx = 1000 * 1000;

void update(int idx, int val){
    while (idx <= MaxIdx){
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

ll lower_eq_than[N];

void init_lower_eq_than() {
	for (int i = 1; i < N; i++) {
		lower_eq_than[i] += lower_eq_than[i - 1];
	}
}

int main() {
	int my_node_id = MyNodeId();

	int n = GetN();
	if (n <= my_node_id) {
		PutLL(0, 0LL);
		Send(0);
		return 0;
	}

	int num_of_nodes = NumberOfNodes();
	int per_node = max(1, n / num_of_nodes); 
	int my_first_pos = my_node_id * per_node;
	int my_last_len = my_node_id < (num_of_nodes - 1)
	                  ? per_node * (my_node_id + 1)
					  : n;

	ll my_non_inversions = 0;

	For (i, my_last_len) {
		int x = GetElement(i);

		if (i == my_first_pos) {
			init_lower_eq_than();
		}
		
		if (i >= my_first_pos) {
			int lower_or_eq_x = read(x);
			my_non_inversions += (ll)lower_or_eq_x;
			my_non_inversions += lower_eq_than[x];
			update(x, 1);
		} else {
			lower_eq_than[x]++;
		}

		// cout << "sum up to: " << x - 1 << ": " << read(x - 1) << "\n";
	}

	// cout << "node: " << my_node_id << ", got non invertions: " << my_non_inversions << endl;

	if (my_node_id != 0) {
		PutLL(0, my_non_inversions);
		Send(0);
		return 0;
	} else {
		for (int i = 1; i < num_of_nodes; i++) {
			Receive(i);
			my_non_inversions += GetLL(i);
		}

		ll res = (ll)n * ((ll)n - 1LL) / 2LL - my_non_inversions;
		cout << res << "\n";
		return 0;
	}
}