#include <bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; int tab[2097155]; const int N_MAX = 1000000; const int base = 1048575; class Tree { public: Tree() { for (int i = base; i >= 1; i--) { tab[i] = tab[2 * i] + tab[2 * i + 1]; } } void insert(int k) { int vk = base + k; while (vk > 0) { tab[vk]++; vk /= 2; } } int query(int k) { int va = base + k + 1; int vb = base + N_MAX + 2; int result = tab[va]; if (va != vb) { result += tab[vb]; } while (va / 2 != vb / 2) { if (va % 2 == 0) { result += tab[va + 1]; } if (vb % 2 == 1) { result += tab[vb - 1]; } va /= 2; vb /= 2; } return result; } }; int main() { int N = GetN(); int numberOfNodes = NumberOfNodes(); int myId = MyNodeId(); int numbersPerNode = N / numberOfNodes + 1; long long sum = 0; int end = min(numbersPerNode * myId, N); for (int i = 0; i < end; i++) { int x = GetElement(i); tab[base + x]++; } Tree t; end = min(numbersPerNode * (myId + 1), N); for (int i = numbersPerNode * myId; i < end; i++) { int x = GetElement(i); sum += t.query(x); t.insert(x); } if (myId == 0) { for (int i = 1; i < numberOfNodes; i++) { Receive(i); sum += GetLL(i); } cout << sum << endl; } else { PutLL(0, sum); Send(0); } return 0; }
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 | #include <bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; int tab[2097155]; const int N_MAX = 1000000; const int base = 1048575; class Tree { public: Tree() { for (int i = base; i >= 1; i--) { tab[i] = tab[2 * i] + tab[2 * i + 1]; } } void insert(int k) { int vk = base + k; while (vk > 0) { tab[vk]++; vk /= 2; } } int query(int k) { int va = base + k + 1; int vb = base + N_MAX + 2; int result = tab[va]; if (va != vb) { result += tab[vb]; } while (va / 2 != vb / 2) { if (va % 2 == 0) { result += tab[va + 1]; } if (vb % 2 == 1) { result += tab[vb - 1]; } va /= 2; vb /= 2; } return result; } }; int main() { int N = GetN(); int numberOfNodes = NumberOfNodes(); int myId = MyNodeId(); int numbersPerNode = N / numberOfNodes + 1; long long sum = 0; int end = min(numbersPerNode * myId, N); for (int i = 0; i < end; i++) { int x = GetElement(i); tab[base + x]++; } Tree t; end = min(numbersPerNode * (myId + 1), N); for (int i = numbersPerNode * myId; i < end; i++) { int x = GetElement(i); sum += t.query(x); t.insert(x); } if (myId == 0) { for (int i = 1; i < numberOfNodes; i++) { Receive(i); sum += GetLL(i); } cout << sum << endl; } else { PutLL(0, sum); Send(0); } return 0; } |