#include <bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; using LL = long long; struct magic_tree { int n; vector <int> data; magic_tree(int new_n) : n(new_n + 1), data(n) {} void add(int x) { x++; while (x > 0) { data[x]++; x -= x & (-x); } } int get(int x) { x++; int result = 0; while (x < n) { result += data[x]; x += x & (-x); } return result; } }; int main() { auto n = GetN(); auto node_id = MyNodeId(); auto nodes = NumberOfNodes(); auto m = n / NumberOfNodes(); auto l = node_id * m; auto r = (node_id + 1) * m; if (node_id == nodes - 1) r = n; LL answer = 0; magic_tree tree(1000 * 1000); vector <int> counter(1000 * 1000); for (auto i = l; i < r; i++) { auto x = GetElement(i) - 1; counter[x]++; tree.add(x); answer += tree.get(x + 1); } for (auto i = 1; i < 1000 * 1000; i++) counter[i] += counter[i - 1]; for (auto i = 0; i < l; i++) { auto x = GetElement(i) - 1; if (x > 0) answer += counter[x - 1]; } if (node_id > 0) { PutLL(0, answer); Send(0); } else { for (auto i = 1; i < nodes; i++) { Receive(i); answer += GetLL(i); } cout << answer << '\n'; } 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 81 82 83 | #include <bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; using LL = long long; struct magic_tree { int n; vector <int> data; magic_tree(int new_n) : n(new_n + 1), data(n) {} void add(int x) { x++; while (x > 0) { data[x]++; x -= x & (-x); } } int get(int x) { x++; int result = 0; while (x < n) { result += data[x]; x += x & (-x); } return result; } }; int main() { auto n = GetN(); auto node_id = MyNodeId(); auto nodes = NumberOfNodes(); auto m = n / NumberOfNodes(); auto l = node_id * m; auto r = (node_id + 1) * m; if (node_id == nodes - 1) r = n; LL answer = 0; magic_tree tree(1000 * 1000); vector <int> counter(1000 * 1000); for (auto i = l; i < r; i++) { auto x = GetElement(i) - 1; counter[x]++; tree.add(x); answer += tree.get(x + 1); } for (auto i = 1; i < 1000 * 1000; i++) counter[i] += counter[i - 1]; for (auto i = 0; i < l; i++) { auto x = GetElement(i) - 1; if (x > 0) answer += counter[x - 1]; } if (node_id > 0) { PutLL(0, answer); Send(0); } else { for (auto i = 1; i < nodes; i++) { Receive(i); answer += GetLL(i); } cout << answer << '\n'; } return 0; } |