#include "message.h" #include "teatr.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; /// test //int GetN() { return int(1e7); } //int GetElement(int i) { return 1000000-i/10; } const int A = 1000000; int f[A+16]; void inc(int i) { for (; i <= A; i += i&-i) ++f[i]; } int get(int i) { int res = 0; for (; i > 0; i -= i&-i) res += f[i]; return res; } ll calc1(int b, int e) { ll res = 0; for (int i = e-1; i >= b; ++i) { int a = GetElement(i); res += get(a-1); inc(a); } return res; } ll calc2(int b1, int b2, int e1, int e2) { ll res = 0; for (int i = b2; i < e2; ++i) { int a = GetElement(i); ++f[a]; } for (int i = 1; i <= A; ++i) f[i] += f[i-1]; for (int i = b1; i < e1; ++i) { int a = GetElement(i); res += f[a-1]; } return res; } int main() { //ios_base::sync_with_stdio(false); //cin.tie(nullptr); cout.tie(nullptr); int num_nodes = NumberOfNodes(); int n = GetN(); int k = 1; while (k*(k+1)/2 < num_nodes) ++k; --k; k = min(k, n); int q = n/k, r = n%k; int num_used = k*(k+1)/2; int nxt = 0; ll ans = 0; vector<int> pos(1, 0); vector<int> b(k), e(k); if (MyNodeId() > num_used) return 0; for (int i = 1; i <= k; ++i) { int sz = q; if (i <= r) ++sz; pos.push_back(pos.back()+sz); } //assert(pos.back() == n); for (int i = 0; i < k; ++i) { b[i] = pos[i]; e[i] = pos[i+1]; } if (MyNodeId() != 0) { int s1, s2; Receive(0); s1 = GetInt(0); s2 = GetInt(0); if (s1 == s2) ans = calc1(b[s1], e[s1]); else ans = calc2(b[s1], e[s1], b[s2], e[s2]); PutLL(0, ans); Send(0); return 0; } for (int i = 0; i < k; ++i) { for (int j = i; j < k; ++j) { ++nxt; PutInt(nxt, i); PutInt(nxt, j); Send(nxt); } } for (int i = 1; i <= num_used; ++i) { Receive(i); ans += GetLL(i); } printf("%lld\n", ans); 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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | #include "message.h" #include "teatr.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; /// test //int GetN() { return int(1e7); } //int GetElement(int i) { return 1000000-i/10; } const int A = 1000000; int f[A+16]; void inc(int i) { for (; i <= A; i += i&-i) ++f[i]; } int get(int i) { int res = 0; for (; i > 0; i -= i&-i) res += f[i]; return res; } ll calc1(int b, int e) { ll res = 0; for (int i = e-1; i >= b; ++i) { int a = GetElement(i); res += get(a-1); inc(a); } return res; } ll calc2(int b1, int b2, int e1, int e2) { ll res = 0; for (int i = b2; i < e2; ++i) { int a = GetElement(i); ++f[a]; } for (int i = 1; i <= A; ++i) f[i] += f[i-1]; for (int i = b1; i < e1; ++i) { int a = GetElement(i); res += f[a-1]; } return res; } int main() { //ios_base::sync_with_stdio(false); //cin.tie(nullptr); cout.tie(nullptr); int num_nodes = NumberOfNodes(); int n = GetN(); int k = 1; while (k*(k+1)/2 < num_nodes) ++k; --k; k = min(k, n); int q = n/k, r = n%k; int num_used = k*(k+1)/2; int nxt = 0; ll ans = 0; vector<int> pos(1, 0); vector<int> b(k), e(k); if (MyNodeId() > num_used) return 0; for (int i = 1; i <= k; ++i) { int sz = q; if (i <= r) ++sz; pos.push_back(pos.back()+sz); } //assert(pos.back() == n); for (int i = 0; i < k; ++i) { b[i] = pos[i]; e[i] = pos[i+1]; } if (MyNodeId() != 0) { int s1, s2; Receive(0); s1 = GetInt(0); s2 = GetInt(0); if (s1 == s2) ans = calc1(b[s1], e[s1]); else ans = calc2(b[s1], e[s1], b[s2], e[s2]); PutLL(0, ans); Send(0); return 0; } for (int i = 0; i < k; ++i) { for (int j = i; j < k; ++j) { ++nxt; PutInt(nxt, i); PutInt(nxt, j); Send(nxt); } } for (int i = 1; i <= num_used; ++i) { Receive(i); ans += GetLL(i); } printf("%lld\n", ans); return 0; } |