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

using namespace std;

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


// Returns sum of arr[0..index]. This function assumes 
// that the array is preprocessed and partial sums of 
// array elements are stored in BITree[]. 
long getSum(long BITree[], long index) 
{ 
    long sum = 0; // Initialize result 
  
    // Traverse ancestors of BITree[index] 
    while (index > 0) 
    { 
        // Add current element of BITree to sum 
        sum += BITree[index]; 
  
        // Move index to parent node in getSum View 
        index -= index & (-index); 
    } 
    return sum; 
} 
  
// Updates a node in Binary Index Tree (BITree) at given index 
// in BITree.  The given value 'val' is added to BITree[i] and 
// all of its ancestors in tree. 
void updateBIT(long BITree[], long n, long index, long val) 
{ 
    // Traverse all ancestors and add 'val' 
    while (index <= n) 
    { 
       // Add 'val' to current node of BI Tree 
       BITree[index] += val; 
  
       // Update index to that of parent in update View 
       index += index & (-index); 
    } 
} 
  

int main() {
//  if(MyNodeId() != 0) return 0;
  long n = GetN();
  long long inversions = 0;
  long long hits = 0;
  long maxElement = 1000000;

  long minEl = MyNodeId() * 10000 + 1;
  long maxEl = (MyNodeId() + 1)*10000;

  
  long BIT[10000+2]; 
    for (long i=1; i<=10001; i++) 
        BIT[i] = 0;

  for(long i=0; i<n; i++) {
	  long el = maxElement - GetElement(i);
	  if (el > maxEl) {
		  inversions += getSum(BIT, 10000);
		  updateBIT(BIT, 10000, 10001, 1);
	  } else if (el >= minEl && el <= maxEl) {
		  inversions += getSum(BIT, el - minEl + 1 - 1);
		  updateBIT(BIT, 10000, el - minEl + 1, 1);
	  }
  }


  if (MyNodeId() > 0) {
    PutLL(0, inversions);
    Send(0);
  } else {
    for (long i = 1; i < NumberOfNodes(); ++i) {
      long instancja = Receive(-1);
      inversions += GetLL(instancja);
    }
    cout << inversions << endl;
  }

  return 0;
}