#include "message.h" #include "teatr.h" #include <vector> #include <algorithm> #include <iostream> using namespace std; /* int GetN() { return 100 * 1000 * 1000; } int GetElement(int i) { if (i < 100 * 1000 * 1000 - 3) return 1 + i / 100; else return 100 * 1000 * 1000 - i; } */ const int MAXH = 1000002; int counter[MAXH]; int greater_than[MAXH]; const int NUMBERS_IN_INSTANCE = 1e6; int N; int INSTANCE; int NODES = 100; int START_ROW; int END_ROW; bool LAST_INSTANCE; inline int get_element(int i) { return GetElement(i - 1); } // źródło: http://rafal-nowak.blogspot.com/2012/12/drzewo-przedziaowe.html class CountingTree { private: typedef unsigned int uint; unsigned const int N; std::vector<unsigned int> T; /** oblicza potege liczby 2, ktora przekracza n Warunek: 0 <= n <= 2*10^9 */ unsigned int UpperPowerOfTwo( const unsigned int n ) const { unsigned int ans = 1; while ( ans<=n ) ans <<= 1; return ans; } public: CountingTree(unsigned int max) : N( UpperPowerOfTwo(max) ), T(N<<1,0) { //fprintf(stderr, "Utworzono drzewo licznikowe o rozmiarze = %d, tzn. maxX = %d\n", T.size(), N-1); } /** liczba wszystkich wstawionych punktów */ unsigned int size() const { return T[1]; } /** sprawdzanie czy w strukturze nie ma ¿adnych punktów */ bool empty() const { return size()==0; } /** dodawanie punktów o wspó³rzêdnej x Argumenty: cnt : liczba punktów do wstawienia, domyœlna wartoœæ = 1 Wynik: liczba punktów mniejszych od x */ unsigned int insert( unsigned int x , int cnt = 1 ) { unsigned int k = N+x, ans = 0; while(k) { T[k] += cnt; if ((k&1)==1) ans += T[k-1]; k >>= 1; } } /** usuwanie punktów o wspó³rzêdnej x Argumenty: cnt : liczba punktów do usuniêcia, domyœlna wartoœæ = 1 Wynik: liczba punktów mniejszych od x */ unsigned int remove( unsigned int x , int cnt = 1 ) { return insert(x,-cnt); } /** k-ty element */ unsigned int select( unsigned int k ) const { uint r = 1; while( r<N ) { r <<= 1; if ( T[r] < k ) k -= T[r++]; } return r-N; } /** liczba punktów równych x */ unsigned int how_many_equal( unsigned int x ) const { return T[N+x]; } /** liczba punktów wiêkszych od x */ unsigned int how_many_greater( unsigned int x ) const { unsigned int k = N+x, ans = 0; while (k>1) { if ((k&1)==0) ans += T[k+1]; k >>= 1; } return ans; } /** liczba punktów mniejszych od x */ unsigned int how_many_less( unsigned int x ) const { return size() - how_many_equal(x) - how_many_greater(x); } }; int main() { N = GetN(); INSTANCE = MyNodeId(); START_ROW = INSTANCE * NUMBERS_IN_INSTANCE + 1; END_ROW = (INSTANCE + 1) * NUMBERS_IN_INSTANCE; if (START_ROW > N) { return 0; } //cout << START_ROW << " " << N << " " << END_ROW << endl; if (START_ROW <= N && N <= END_ROW) { LAST_INSTANCE = true; } CountingTree counter_tree = CountingTree(NUMBERS_IN_INSTANCE); long long instanceResult = 0; for (int i = START_ROW; i <= min(END_ROW, N); ++i) { int h = get_element(i); counter[h]++; instanceResult += counter_tree.how_many_greater(h); //cout << "H " << h << "GREATER" << counter_tree.how_many_greater(h) << endl; counter_tree.insert(h); } for (int i = MAXH; i > 0; i--) { greater_than[i] = greater_than[i + 1] + counter[i + 1]; } long long nextResult = 0; //cout << INSTANCE << LAST_INSTANCE << endl; if (!LAST_INSTANCE) { for (int i = END_ROW + 1; i <= N; ++i) { int h = get_element(i); nextResult += greater_than[h]; } } long long previousResult = 0; if (INSTANCE > 0) { Receive(INSTANCE - 1); previousResult = GetLL(INSTANCE - 1); } long long finalResult = instanceResult + nextResult + previousResult; if (!LAST_INSTANCE) { PutLL(INSTANCE + 1, finalResult); Send(INSTANCE + 1); } else { cout << finalResult << endl; } }
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 151 152 153 | #include "message.h" #include "teatr.h" #include <vector> #include <algorithm> #include <iostream> using namespace std; /* int GetN() { return 100 * 1000 * 1000; } int GetElement(int i) { if (i < 100 * 1000 * 1000 - 3) return 1 + i / 100; else return 100 * 1000 * 1000 - i; } */ const int MAXH = 1000002; int counter[MAXH]; int greater_than[MAXH]; const int NUMBERS_IN_INSTANCE = 1e6; int N; int INSTANCE; int NODES = 100; int START_ROW; int END_ROW; bool LAST_INSTANCE; inline int get_element(int i) { return GetElement(i - 1); } // źródło: http://rafal-nowak.blogspot.com/2012/12/drzewo-przedziaowe.html class CountingTree { private: typedef unsigned int uint; unsigned const int N; std::vector<unsigned int> T; /** oblicza potege liczby 2, ktora przekracza n Warunek: 0 <= n <= 2*10^9 */ unsigned int UpperPowerOfTwo( const unsigned int n ) const { unsigned int ans = 1; while ( ans<=n ) ans <<= 1; return ans; } public: CountingTree(unsigned int max) : N( UpperPowerOfTwo(max) ), T(N<<1,0) { //fprintf(stderr, "Utworzono drzewo licznikowe o rozmiarze = %d, tzn. maxX = %d\n", T.size(), N-1); } /** liczba wszystkich wstawionych punktów */ unsigned int size() const { return T[1]; } /** sprawdzanie czy w strukturze nie ma ¿adnych punktów */ bool empty() const { return size()==0; } /** dodawanie punktów o wspó³rzêdnej x Argumenty: cnt : liczba punktów do wstawienia, domyœlna wartoœæ = 1 Wynik: liczba punktów mniejszych od x */ unsigned int insert( unsigned int x , int cnt = 1 ) { unsigned int k = N+x, ans = 0; while(k) { T[k] += cnt; if ((k&1)==1) ans += T[k-1]; k >>= 1; } } /** usuwanie punktów o wspó³rzêdnej x Argumenty: cnt : liczba punktów do usuniêcia, domyœlna wartoœæ = 1 Wynik: liczba punktów mniejszych od x */ unsigned int remove( unsigned int x , int cnt = 1 ) { return insert(x,-cnt); } /** k-ty element */ unsigned int select( unsigned int k ) const { uint r = 1; while( r<N ) { r <<= 1; if ( T[r] < k ) k -= T[r++]; } return r-N; } /** liczba punktów równych x */ unsigned int how_many_equal( unsigned int x ) const { return T[N+x]; } /** liczba punktów wiêkszych od x */ unsigned int how_many_greater( unsigned int x ) const { unsigned int k = N+x, ans = 0; while (k>1) { if ((k&1)==0) ans += T[k+1]; k >>= 1; } return ans; } /** liczba punktów mniejszych od x */ unsigned int how_many_less( unsigned int x ) const { return size() - how_many_equal(x) - how_many_greater(x); } }; int main() { N = GetN(); INSTANCE = MyNodeId(); START_ROW = INSTANCE * NUMBERS_IN_INSTANCE + 1; END_ROW = (INSTANCE + 1) * NUMBERS_IN_INSTANCE; if (START_ROW > N) { return 0; } //cout << START_ROW << " " << N << " " << END_ROW << endl; if (START_ROW <= N && N <= END_ROW) { LAST_INSTANCE = true; } CountingTree counter_tree = CountingTree(NUMBERS_IN_INSTANCE); long long instanceResult = 0; for (int i = START_ROW; i <= min(END_ROW, N); ++i) { int h = get_element(i); counter[h]++; instanceResult += counter_tree.how_many_greater(h); //cout << "H " << h << "GREATER" << counter_tree.how_many_greater(h) << endl; counter_tree.insert(h); } for (int i = MAXH; i > 0; i--) { greater_than[i] = greater_than[i + 1] + counter[i + 1]; } long long nextResult = 0; //cout << INSTANCE << LAST_INSTANCE << endl; if (!LAST_INSTANCE) { for (int i = END_ROW + 1; i <= N; ++i) { int h = get_element(i); nextResult += greater_than[h]; } } long long previousResult = 0; if (INSTANCE > 0) { Receive(INSTANCE - 1); previousResult = GetLL(INSTANCE - 1); } long long finalResult = instanceResult + nextResult + previousResult; if (!LAST_INSTANCE) { PutLL(INSTANCE + 1, finalResult); Send(INSTANCE + 1); } else { cout << finalResult << endl; } } |