#include <bits/stdc++.h> #include "message.h" #include "teatr.h" #define FOR(i, a, b) for (int i=(a); (i)<(b); (i)++) #define PPC(x) __builtin_popcountll((x)) #define ALL(x) (x).begin(), (x).end() #define pb push_back using namespace std; const int maxN = 100000000, totalRan = 1000000;//, insta = 100, ran = totalRan / insta; int insta, ran; long long res, T[totalRan + 42]; /*int GetN() { return maxN; } int GetElement(int i) { return i % totalRan + 1; } */ void updt(int i) { for (i++; i<=ran; i+=(-i)&i) T[i]++; } long long sum(int i) { long long ret = 0; for (; i!=0; i&=i-1) ret+=T[i]; return ret; } void marge(int ja) { for (int m=1; m<insta; m<<=1) { int w = ja^m; if (m & ja) { PutLL(w, res); Send(w); exit(0); } if (w < insta) { Receive(w); res += GetLL(w); } } } int main() { insta = NumberOfNodes(); ran = totalRan / insta; int ja = MyNodeId(); int p = ran * ja + 1; long long all = 0; for (int i=GetN()-1; i>=0; i--) { int v = GetElement(i) - p; if (v >= ran) res += all; else if (v >= 0) { res += sum(v); updt(v); all++; } } marge(ja); printf("%lld\n", res); 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 | #include <bits/stdc++.h> #include "message.h" #include "teatr.h" #define FOR(i, a, b) for (int i=(a); (i)<(b); (i)++) #define PPC(x) __builtin_popcountll((x)) #define ALL(x) (x).begin(), (x).end() #define pb push_back using namespace std; const int maxN = 100000000, totalRan = 1000000;//, insta = 100, ran = totalRan / insta; int insta, ran; long long res, T[totalRan + 42]; /*int GetN() { return maxN; } int GetElement(int i) { return i % totalRan + 1; } */ void updt(int i) { for (i++; i<=ran; i+=(-i)&i) T[i]++; } long long sum(int i) { long long ret = 0; for (; i!=0; i&=i-1) ret+=T[i]; return ret; } void marge(int ja) { for (int m=1; m<insta; m<<=1) { int w = ja^m; if (m & ja) { PutLL(w, res); Send(w); exit(0); } if (w < insta) { Receive(w); res += GetLL(w); } } } int main() { insta = NumberOfNodes(); ran = totalRan / insta; int ja = MyNodeId(); int p = ran * ja + 1; long long all = 0; for (int i=GetN()-1; i>=0; i--) { int v = GetElement(i) - p; if (v >= ran) res += all; else if (v >= 0) { res += sum(v); updt(v); all++; } } marge(ja); printf("%lld\n", res); return 0; } |