#include "message.h" #include "teatr.h" #include <iostream> using namespace std; long long n; long long wynik; const int R = 1048576; int drzewo[2*R]; long long sumySuf[1000 * 1000 + 2]; long long zliczone[1000 * 1000 + 2]; void update(int x) { x += R; drzewo[x]++; while(x > 1) { x /= 2; drzewo[x] = drzewo[2*x] + drzewo[2*x + 1]; } } long long query(int x) { int a = x + R; int b = 1000 * 1000 + R + 100; long long w = drzewo[a]; if(a != b) w += drzewo[b]; while(a / 2 != b / 2) { if(a % 2 == 0) w += drzewo[a + 1]; if(b % 2 == 1) w += drzewo[b - 1]; a /= 2; b /= 2; } return w; } void aktualizujSumy() { for(int i = 1000 * 1000; i > 0; i--) { sumySuf[i] = sumySuf[i + 1] + zliczone[i]; } } void dodajISprawdz(int x) { aktualizujSumy(); for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) { int t = GetElement(i); wynik += sumySuf[t + 1]; zliczone[t]++; } } void dodajBezSprawdzania(int x) { aktualizujSumy(); for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) { int t = GetElement(i); zliczone[t]++; } } void sprawdzBezDodawania(int x) { aktualizujSumy(); for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) { int t = GetElement(i); wynik += sumySuf[t + 1]; } } int main() { n = GetN(); for(int i = n * MyNodeId() / NumberOfNodes(); i < n * (MyNodeId() + 1) / NumberOfNodes(); i++) { int t = GetElement(i); wynik += query(t + 1); update(t); zliczone[t]++; } if(MyNodeId() % 10 == 0) { for(int i = MyNodeId() + 1; i < MyNodeId() + 10; i++) { dodajISprawdz(i); } } else { for(int i = (MyNodeId() / 10) * 10; i < (MyNodeId() / 10) * 10 + 10; i++) { if(i == MyNodeId()) continue; dodajBezSprawdzania(i); } } for(int i = MyNodeId() + 10; i < 100; i += 10) { sprawdzBezDodawania(i); } if(MyNodeId() == 0){ for(int i = 1; i < NumberOfNodes(); i++) { int nr = Receive(-1); wynik += GetLL(nr); } cout << wynik; } else { PutLL(0, wynik); Send(0); } 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 | #include "message.h" #include "teatr.h" #include <iostream> using namespace std; long long n; long long wynik; const int R = 1048576; int drzewo[2*R]; long long sumySuf[1000 * 1000 + 2]; long long zliczone[1000 * 1000 + 2]; void update(int x) { x += R; drzewo[x]++; while(x > 1) { x /= 2; drzewo[x] = drzewo[2*x] + drzewo[2*x + 1]; } } long long query(int x) { int a = x + R; int b = 1000 * 1000 + R + 100; long long w = drzewo[a]; if(a != b) w += drzewo[b]; while(a / 2 != b / 2) { if(a % 2 == 0) w += drzewo[a + 1]; if(b % 2 == 1) w += drzewo[b - 1]; a /= 2; b /= 2; } return w; } void aktualizujSumy() { for(int i = 1000 * 1000; i > 0; i--) { sumySuf[i] = sumySuf[i + 1] + zliczone[i]; } } void dodajISprawdz(int x) { aktualizujSumy(); for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) { int t = GetElement(i); wynik += sumySuf[t + 1]; zliczone[t]++; } } void dodajBezSprawdzania(int x) { aktualizujSumy(); for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) { int t = GetElement(i); zliczone[t]++; } } void sprawdzBezDodawania(int x) { aktualizujSumy(); for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) { int t = GetElement(i); wynik += sumySuf[t + 1]; } } int main() { n = GetN(); for(int i = n * MyNodeId() / NumberOfNodes(); i < n * (MyNodeId() + 1) / NumberOfNodes(); i++) { int t = GetElement(i); wynik += query(t + 1); update(t); zliczone[t]++; } if(MyNodeId() % 10 == 0) { for(int i = MyNodeId() + 1; i < MyNodeId() + 10; i++) { dodajISprawdz(i); } } else { for(int i = (MyNodeId() / 10) * 10; i < (MyNodeId() / 10) * 10 + 10; i++) { if(i == MyNodeId()) continue; dodajBezSprawdzania(i); } } for(int i = MyNodeId() + 10; i < 100; i += 10) { sprawdzBezDodawania(i); } if(MyNodeId() == 0){ for(int i = 1; i < NumberOfNodes(); i++) { int nr = Receive(-1); wynik += GetLL(nr); } cout << wynik; } else { PutLL(0, wynik); Send(0); } return 0; } |