#include<bits/stdc++.h> #include<message.h> #include<teatr.h> #define lim 1000009 #define pot 1048576 using namespace std; int n,t[pot*2+9]; int main() { int Instance = MyNodeId(); n = GetN(); int Nd = NumberOfNodes(); int ml = n/Nd*Instance; int mp = n/Nd*(Instance+1); if(Instance==Nd-1) { mp = n; } for(int i = 0;i<ml;++i) { ++t[pot+GetElement(i)]; } for(int i = pot-1;i>0;--i) { t[i] = t[i*2]+t[i*2+1]; } long long w = 0; for(int ii = ml;ii<mp;++ii) { int k = GetElement(ii); int i = pot+k+1; int j = pot*2-1; int s = 0; while(i<j) { if(i&1) { s += t[i]; ++i; } j >>= 1; i >>= 1; } if(i==j) { s += t[j]; } w += s; i = pot+k; while(i>0) { ++t[i]; i >>= 1; } } if(Instance==Nd-1) { for(int i = 0;i<Nd-1;++i) { Receive(i); w += GetLL(i); } printf("%lld\n", w); return 0; } else { PutLL(Nd-1,w); Send(Nd-1); } }
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 | #include<bits/stdc++.h> #include<message.h> #include<teatr.h> #define lim 1000009 #define pot 1048576 using namespace std; int n,t[pot*2+9]; int main() { int Instance = MyNodeId(); n = GetN(); int Nd = NumberOfNodes(); int ml = n/Nd*Instance; int mp = n/Nd*(Instance+1); if(Instance==Nd-1) { mp = n; } for(int i = 0;i<ml;++i) { ++t[pot+GetElement(i)]; } for(int i = pot-1;i>0;--i) { t[i] = t[i*2]+t[i*2+1]; } long long w = 0; for(int ii = ml;ii<mp;++ii) { int k = GetElement(ii); int i = pot+k+1; int j = pot*2-1; int s = 0; while(i<j) { if(i&1) { s += t[i]; ++i; } j >>= 1; i >>= 1; } if(i==j) { s += t[j]; } w += s; i = pot+k; while(i>0) { ++t[i]; i >>= 1; } } if(Instance==Nd-1) { for(int i = 0;i<Nd-1;++i) { Receive(i); w += GetLL(i); } printf("%lld\n", w); return 0; } else { PutLL(Nd-1,w); Send(Nd-1); } } |