#include <iostream> #include <vector> #include "message.h" #include "teatr.h" using namespace std; const int SIZE = 10000; const int MAX = SIZE + 500; int fenwick[MAX]; void upd(int index) { while(index <= SIZE) { fenwick[index] += 1LL; index += index & (-index); } } long long suma(int index) { long long ans = 0; while(index > 0) { ans += fenwick[index]; index -= index & (-index); } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; long long ans = 0; long long mniejsze = 0; N = GetN(); int limdol = MyNodeId() * SIZE + 1; int limgora = (MyNodeId() + 1LL) * SIZE; if(MyNodeId() > 0) { int liczba; for(int i = N - 1; i >= 0; --i) { liczba = GetElement(i); if(liczba > limgora)continue; if(liczba < limdol) { ++mniejsze; } else { int liczba2 = liczba % SIZE; if(liczba2 <= 0)liczba2 += SIZE; if(liczba >= limdol)ans += suma(liczba % SIZE); ans += mniejsze; upd(liczba2); } } PutLL(0, ans); Send(0); } else { int liczba; for(int i = N - 1; i >= 0; --i) { liczba = GetElement(i); if(liczba > limgora)continue; if(liczba < limdol) { ++mniejsze; } else { int liczba2 = liczba % SIZE; if(liczba2 <= 0)liczba2 += SIZE; liczba = liczba - 1; if(liczba >= limdol)ans += suma(liczba % SIZE); ans += mniejsze; upd(liczba2); } } for(int i = 1; i < NumberOfNodes(); ++i) { Receive(i); ans += GetLL(i); } cout << ans; } 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 | #include <iostream> #include <vector> #include "message.h" #include "teatr.h" using namespace std; const int SIZE = 10000; const int MAX = SIZE + 500; int fenwick[MAX]; void upd(int index) { while(index <= SIZE) { fenwick[index] += 1LL; index += index & (-index); } } long long suma(int index) { long long ans = 0; while(index > 0) { ans += fenwick[index]; index -= index & (-index); } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; long long ans = 0; long long mniejsze = 0; N = GetN(); int limdol = MyNodeId() * SIZE + 1; int limgora = (MyNodeId() + 1LL) * SIZE; if(MyNodeId() > 0) { int liczba; for(int i = N - 1; i >= 0; --i) { liczba = GetElement(i); if(liczba > limgora)continue; if(liczba < limdol) { ++mniejsze; } else { int liczba2 = liczba % SIZE; if(liczba2 <= 0)liczba2 += SIZE; if(liczba >= limdol)ans += suma(liczba % SIZE); ans += mniejsze; upd(liczba2); } } PutLL(0, ans); Send(0); } else { int liczba; for(int i = N - 1; i >= 0; --i) { liczba = GetElement(i); if(liczba > limgora)continue; if(liczba < limdol) { ++mniejsze; } else { int liczba2 = liczba % SIZE; if(liczba2 <= 0)liczba2 += SIZE; liczba = liczba - 1; if(liczba >= limdol)ans += suma(liczba % SIZE); ans += mniejsze; upd(liczba2); } } for(int i = 1; i < NumberOfNodes(); ++i) { Receive(i); ans += GetLL(i); } cout << ans; } return 0; } |