#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <set> #include <cmath> #include "teatr.h" #include "message.h" using namespace std; typedef vector<int> VI; typedef unsigned long long LL; #define FOR(x, b, e) for (int x = b; x <= (e); ++x) #define FORD(x, b, e) for (int x = b; x >= (e); --x) #define REP(x, n) for (int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second const int MAX_SIZE = 1000000; class Solver { public: int n, nodes, start, end; void readInput() { n = GetN(); nodes = n / MAX_SIZE; if(n % MAX_SIZE > 0) nodes++; start = MyNodeId() * MAX_SIZE; end = min(n, start + MAX_SIZE); } LL merge(VI &a, VI &b, int left, int right) { int ave = left + (right - left) / 2; for (int i = left; i < right; i++) { b[i] = a[i]; } int i = left; int j = left; int k = ave; LL result = 0; while (i < right) { if (j == ave) { while (i < right) { a[i++] = b[k++]; } } else if (k == right) { while (i < right) { a[i++] = b[j++]; } } else if (b[j] <= b[k]) { a[i++] = b[j++]; } else { result += ave - j; a[i++] = b[k++]; } } return result; } LL getInversions(VI &a, VI &b, int left, int right) { LL inversions = 0; if (right <= left + 1) return inversions; int ave = left + (right - left) / 2; inversions += getInversions(a, b, left, ave); inversions += getInversions(a, b, ave, right); inversions += merge(a, b, left, right); return inversions; } void solve() { if(MyNodeId() >= nodes) return; VI data(end - start); VI tmp(end - start); REP(i, data.size()) { data[i] = GetElement(start + i); } LL result = getInversions(data, tmp, 0, data.size()); VI numbers(MAX_SIZE + 1, 0); for(int i = end; i < n; i++) { numbers[GetElement(i)]++; } for(int i = 1; i < numbers.size(); i++) { numbers[i] += numbers[i - 1]; } REP(i, data.size()) { result += numbers[data[i] - 1]; } if(MyNodeId() < nodes - 1) { PutLL(nodes - 1, result); Send(nodes - 1); } else { for(int i = nodes - 2; i >= 0; i--) { Receive(i); result += GetLL(i); } cout << result << '\n'; } } }; int main() { ios_base::sync_with_stdio(0); Solver solver; solver.readInput(); solver.solve(); 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 | #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <set> #include <cmath> #include "teatr.h" #include "message.h" using namespace std; typedef vector<int> VI; typedef unsigned long long LL; #define FOR(x, b, e) for (int x = b; x <= (e); ++x) #define FORD(x, b, e) for (int x = b; x >= (e); --x) #define REP(x, n) for (int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second const int MAX_SIZE = 1000000; class Solver { public: int n, nodes, start, end; void readInput() { n = GetN(); nodes = n / MAX_SIZE; if(n % MAX_SIZE > 0) nodes++; start = MyNodeId() * MAX_SIZE; end = min(n, start + MAX_SIZE); } LL merge(VI &a, VI &b, int left, int right) { int ave = left + (right - left) / 2; for (int i = left; i < right; i++) { b[i] = a[i]; } int i = left; int j = left; int k = ave; LL result = 0; while (i < right) { if (j == ave) { while (i < right) { a[i++] = b[k++]; } } else if (k == right) { while (i < right) { a[i++] = b[j++]; } } else if (b[j] <= b[k]) { a[i++] = b[j++]; } else { result += ave - j; a[i++] = b[k++]; } } return result; } LL getInversions(VI &a, VI &b, int left, int right) { LL inversions = 0; if (right <= left + 1) return inversions; int ave = left + (right - left) / 2; inversions += getInversions(a, b, left, ave); inversions += getInversions(a, b, ave, right); inversions += merge(a, b, left, right); return inversions; } void solve() { if(MyNodeId() >= nodes) return; VI data(end - start); VI tmp(end - start); REP(i, data.size()) { data[i] = GetElement(start + i); } LL result = getInversions(data, tmp, 0, data.size()); VI numbers(MAX_SIZE + 1, 0); for(int i = end; i < n; i++) { numbers[GetElement(i)]++; } for(int i = 1; i < numbers.size(); i++) { numbers[i] += numbers[i - 1]; } REP(i, data.size()) { result += numbers[data[i] - 1]; } if(MyNodeId() < nodes - 1) { PutLL(nodes - 1, result); Send(nodes - 1); } else { for(int i = nodes - 2; i >= 0; i--) { Receive(i); result += GetLL(i); } cout << result << '\n'; } } }; int main() { ios_base::sync_with_stdio(0); Solver solver; solver.readInput(); solver.solve(); return 0; } |