#include <iostream> #include "message.h" #include "teatr.h" using namespace std; typedef long long LL; const int E=1000001; int drzewo[2*1048576], pierwLisc; int pierwszyLisc(int lEltow) { for (int wyn=1; ; wyn*=2) if (lEltow<=wyn) return wyn; } void zbudujDrzewo() { for (int i=pierwLisc-1; 0<i; --i) drzewo[i]=drzewo[i*2]+drzewo[i*2+1]; } int wstaw(int w) { w+=pierwLisc; int wyn=0; while (1<w) { ++drzewo[w]; if (w%2==0) wyn+=drzewo[w+1]; w/=2; } return wyn; } int main() { pierwLisc=pierwszyLisc(E); int n=GetN(); int pocz=LL(MyNodeId())*n/NumberOfNodes(), kon=LL(MyNodeId()+1)*n/NumberOfNodes(); for (int i=0; i<pocz; ++i) ++drzewo[pierwLisc+GetElement(i)]; zbudujDrzewo(); long long wyn=0; for (int i=pocz; i<kon; ++i) wyn+=wstaw(GetElement(i)); if (MyNodeId()==0) { for (int i=1; i<NumberOfNodes(); ++i) wyn+=GetLL(Receive(-1)); cout<<wyn<<endl; } else { PutLL(0, wyn); 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 | #include <iostream> #include "message.h" #include "teatr.h" using namespace std; typedef long long LL; const int E=1000001; int drzewo[2*1048576], pierwLisc; int pierwszyLisc(int lEltow) { for (int wyn=1; ; wyn*=2) if (lEltow<=wyn) return wyn; } void zbudujDrzewo() { for (int i=pierwLisc-1; 0<i; --i) drzewo[i]=drzewo[i*2]+drzewo[i*2+1]; } int wstaw(int w) { w+=pierwLisc; int wyn=0; while (1<w) { ++drzewo[w]; if (w%2==0) wyn+=drzewo[w+1]; w/=2; } return wyn; } int main() { pierwLisc=pierwszyLisc(E); int n=GetN(); int pocz=LL(MyNodeId())*n/NumberOfNodes(), kon=LL(MyNodeId()+1)*n/NumberOfNodes(); for (int i=0; i<pocz; ++i) ++drzewo[pierwLisc+GetElement(i)]; zbudujDrzewo(); long long wyn=0; for (int i=pocz; i<kon; ++i) wyn+=wstaw(GetElement(i)); if (MyNodeId()==0) { for (int i=1; i<NumberOfNodes(); ++i) wyn+=GetLL(Receive(-1)); cout<<wyn<<endl; } else { PutLL(0, wyn); Send(0); } return 0; } |