#include <bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; typedef long long ll; const int len = 1000000; const int p = (1<<20); int n, i, x, a, b, id; int suf [1000002]; int tree [p+p]; ll out; int sum (int l, int r) { l+=p; r+=p; int res = tree[l]+tree[r]; while (l/2!=r/2) { if (l%2==0) res+=tree[l+1]; if (r%2==1) res+=tree[r-1]; l/=2; r/=2; } return res; } void inc (int u){ for (u+=p; u!=0; u/=2) tree[u]++; } int main () { id = MyNodeId(); n = GetN(); a = len*id; b = min(n, a+len); if (a>=n) return PutLL(0, 0), Send(0), 0; for (i=a; i<b; i++) { x = GetElement(i); out += (ll)(sum(x+1, 1000002)); inc(x); } for (i=1000000; i>=0; i--) suf[i]=suf[i+1]+tree[i+p]; for (i=b; i<n; i++) { x = GetElement(i); out += (ll)(suf[x+1]); } if (id!=0) return PutLL(0, out), Send(0), 0; x = NumberOfNodes()-1; while (x--) out += GetLL(Receive(-1)); printf ("%lld\n",out); 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 | #include <bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; typedef long long ll; const int len = 1000000; const int p = (1<<20); int n, i, x, a, b, id; int suf [1000002]; int tree [p+p]; ll out; int sum (int l, int r) { l+=p; r+=p; int res = tree[l]+tree[r]; while (l/2!=r/2) { if (l%2==0) res+=tree[l+1]; if (r%2==1) res+=tree[r-1]; l/=2; r/=2; } return res; } void inc (int u){ for (u+=p; u!=0; u/=2) tree[u]++; } int main () { id = MyNodeId(); n = GetN(); a = len*id; b = min(n, a+len); if (a>=n) return PutLL(0, 0), Send(0), 0; for (i=a; i<b; i++) { x = GetElement(i); out += (ll)(sum(x+1, 1000002)); inc(x); } for (i=1000000; i>=0; i--) suf[i]=suf[i+1]+tree[i+p]; for (i=b; i<n; i++) { x = GetElement(i); out += (ll)(suf[x+1]); } if (id!=0) return PutLL(0, out), Send(0), 0; x = NumberOfNodes()-1; while (x--) out += GetLL(Receive(-1)); printf ("%lld\n",out); return 0; } |