#include "message.h" #include "teatr.h" #include <bits/stdc++.h> using namespace std; typedef long long LL; LL globans = 0; const int N = 1e6 + 2; int n, cnt[N + 7], tree[N + 7]; void update(int id) { for(int i = id + 1; i <= N; i += (i & -i)) tree[i]++; } int pref(int x) { x++; int res = 0; for(int i = x; i; i -= (i & -i)) res += tree[i]; return res; } void run() { n = GetN(); int d = (n + NumberOfNodes() - 1) / NumberOfNodes(); int my = MyNodeId(); int from = my * d, to = min(n, (my + 1) * d); if(from >= to) { PutLL(0, 0); Send(0); return; } LL ans = 0; for(int i = 0; i <= N; i++) { tree[i] = cnt[i] = 0; } for(int i = 0; i < from; i++) { cnt[GetElement(i)]++; } for(int i = N; i; i--) { cnt[i] += cnt[i + 1]; } for(int i = from; i < to; i++) { int x = GetElement(i); update(x); ans += (i - from + 1) - pref(x); ans += cnt[x + 1]; } if(my > 0) { PutLL(0, ans); Send(0); } else { for(int i = 1; i < NumberOfNodes(); i++) { int re = Receive(i); ans += GetLL(re); } } globans += ans; } int main() { run(); if(MyNodeId() == 0) printf("%lld\n", globans); 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 | #include "message.h" #include "teatr.h" #include <bits/stdc++.h> using namespace std; typedef long long LL; LL globans = 0; const int N = 1e6 + 2; int n, cnt[N + 7], tree[N + 7]; void update(int id) { for(int i = id + 1; i <= N; i += (i & -i)) tree[i]++; } int pref(int x) { x++; int res = 0; for(int i = x; i; i -= (i & -i)) res += tree[i]; return res; } void run() { n = GetN(); int d = (n + NumberOfNodes() - 1) / NumberOfNodes(); int my = MyNodeId(); int from = my * d, to = min(n, (my + 1) * d); if(from >= to) { PutLL(0, 0); Send(0); return; } LL ans = 0; for(int i = 0; i <= N; i++) { tree[i] = cnt[i] = 0; } for(int i = 0; i < from; i++) { cnt[GetElement(i)]++; } for(int i = N; i; i--) { cnt[i] += cnt[i + 1]; } for(int i = from; i < to; i++) { int x = GetElement(i); update(x); ans += (i - from + 1) - pref(x); ans += cnt[x + 1]; } if(my > 0) { PutLL(0, ans); Send(0); } else { for(int i = 1; i < NumberOfNodes(); i++) { int re = Receive(i); ans += GetLL(re); } } globans += ans; } int main() { run(); if(MyNodeId() == 0) printf("%lld\n", globans); return 0; } |