#include "message.h" #include "teatr.h" #include <iostream> #include <vector> class MyTree { private: std::vector<std::vector<int>> data; public: MyTree(int size) { while (size > 1) { data.push_back(std::vector<int>(size, 0)); size = size/2 + (size%2 == 0 ? 0 : 1); } } void add(int value) { for (int i = 0; i < data.size(); ++i) { data[i][value] += 1; value /= 2; } } int query(const int value) { int ret = data[0][value]; int x = value; int mask = 1; for (int i = 0; i < data.size(); ++i) { if (mask&value) ret += data[i][x-1]; mask *= 2; x /= 2; } return ret; } }; void run() { using namespace std; const int nodes = NumberOfNodes(); const int id = MyNodeId(); const int n = GetN(); std::vector<std::pair<int, int>> easy_tasks; for (int i = 0; i < nodes; ++i) for (int j = 0; j < nodes; ++j) { if (i < j) easy_tasks.push_back({i, j}); } { long long answer = 0; vector<int> counts(1000002, 0); int counted_i = -1; auto solve_easy_task = [&](int i1, int i2) { if (i1 != counted_i) { counted_i = i1; fill(counts.begin(), counts.end(), 0); const int begin1 = 1LL * (i1) * n / nodes; const int end1 = 1LL * (i1+1) * n / nodes; for (int pos = begin1; pos != end1; ++pos) counts[GetElement(pos)] += 1; for (int size = 1000000; size >= 0; --size) counts[size] += counts[size+1]; } const int begin2 = 1LL * (i2) * n / nodes; const int end2 = 1LL * (i2+1) * n / nodes; for (int pos = begin2; pos != end2; ++pos) answer += counts[GetElement(pos)+1]; }; auto solve_hard_task = [&](int i) { const int begin = 1LL * (i) * n / nodes; const int end = 1LL * (i+1) * n / nodes; MyTree tree(1000002); int count = 0; for (int pos = begin; pos != end; ++pos) { const int e = GetElement(pos); tree.add(e); count += 1; answer += (count - tree.query(e)); } }; const int begin = 1LL * (id) * easy_tasks.size() / nodes; const int end = 1LL * (id+1) * easy_tasks.size() / nodes; for (int i = begin; i < end; ++i) solve_easy_task(easy_tasks[i].first, easy_tasks[i].second); solve_hard_task(id); PutLL(0, answer); Send(0); } if (id != 0) return; long long total = 0; for (int i = 0; i < nodes; ++i) { const int source = Receive(-1); total += GetLL(source); } cout << total << endl; } int main() { run(); 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 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 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 | #include "message.h" #include "teatr.h" #include <iostream> #include <vector> class MyTree { private: std::vector<std::vector<int>> data; public: MyTree(int size) { while (size > 1) { data.push_back(std::vector<int>(size, 0)); size = size/2 + (size%2 == 0 ? 0 : 1); } } void add(int value) { for (int i = 0; i < data.size(); ++i) { data[i][value] += 1; value /= 2; } } int query(const int value) { int ret = data[0][value]; int x = value; int mask = 1; for (int i = 0; i < data.size(); ++i) { if (mask&value) ret += data[i][x-1]; mask *= 2; x /= 2; } return ret; } }; void run() { using namespace std; const int nodes = NumberOfNodes(); const int id = MyNodeId(); const int n = GetN(); std::vector<std::pair<int, int>> easy_tasks; for (int i = 0; i < nodes; ++i) for (int j = 0; j < nodes; ++j) { if (i < j) easy_tasks.push_back({i, j}); } { long long answer = 0; vector<int> counts(1000002, 0); int counted_i = -1; auto solve_easy_task = [&](int i1, int i2) { if (i1 != counted_i) { counted_i = i1; fill(counts.begin(), counts.end(), 0); const int begin1 = 1LL * (i1) * n / nodes; const int end1 = 1LL * (i1+1) * n / nodes; for (int pos = begin1; pos != end1; ++pos) counts[GetElement(pos)] += 1; for (int size = 1000000; size >= 0; --size) counts[size] += counts[size+1]; } const int begin2 = 1LL * (i2) * n / nodes; const int end2 = 1LL * (i2+1) * n / nodes; for (int pos = begin2; pos != end2; ++pos) answer += counts[GetElement(pos)+1]; }; auto solve_hard_task = [&](int i) { const int begin = 1LL * (i) * n / nodes; const int end = 1LL * (i+1) * n / nodes; MyTree tree(1000002); int count = 0; for (int pos = begin; pos != end; ++pos) { const int e = GetElement(pos); tree.add(e); count += 1; answer += (count - tree.query(e)); } }; const int begin = 1LL * (id) * easy_tasks.size() / nodes; const int end = 1LL * (id+1) * easy_tasks.size() / nodes; for (int i = begin; i < end; ++i) solve_easy_task(easy_tasks[i].first, easy_tasks[i].second); solve_hard_task(id); PutLL(0, answer); Send(0); } if (id != 0) return; long long total = 0; for (int i = 0; i < nodes; ++i) { const int source = Receive(-1); total += GetLL(source); } cout << total << endl; } int main() { run(); return 0; } |