#include <bits/stdc++.h> #include "teatr.h" #include "message.h" #define forn(i, n) for(int i = 0; i < n; ++i) using namespace std; typedef long long ll; typedef pair<int, int> pint; int n = 1000042; // array size ll t[2000042]; void inc(int p) { // increase value at position p for (t[p += n] += 1; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1]; } ll query(int l, int r) { // sum on interval [l, r) ll res = 0; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l&1) res += t[l++]; if (r&1) res += t[--r]; } return res; } map<ll,ll> sizes; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int myId = 0; //// myId = MyNodeId(); //// ll N = 0; //// //cin >> N; N = GetN(); //// ll myConfl = 0; for (int i=min(N - 1, (myId+1) * 1000000LL - 1); i >= myId * 1000000LL; i--) { ll el; //// //cin >> el; el = GetElement(i); //// myConfl += query(1, el); inc(el); if (sizes.size() <= 900) { sizes[el]++; } } if (myId < 99) // recive { Receive(myId+1); ll itsConfl = GetLL(myId+1); myConfl += itsConfl; ll k = GetLL(myId+1); for (int i=0; i<k; i++) { ll wzrost = GetLL(myId+1); ll ile = GetLL(myId+1); myConfl += query(wzrost, 1000001)*ile; sizes[wzrost] += ile; } } if (myId > 0) // send { PutLL(myId-1, myConfl); if (sizes.size() <= 900) { PutLL(myId-1, sizes.size()); for (auto el : sizes) { PutLL(myId-1, el.first); PutLL(myId-1, el.second); } } else { PutLL(myId-1, 0); } Send(myId-1); } if (myId == 0) // cout { cout << myConfl; } 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 <bits/stdc++.h> #include "teatr.h" #include "message.h" #define forn(i, n) for(int i = 0; i < n; ++i) using namespace std; typedef long long ll; typedef pair<int, int> pint; int n = 1000042; // array size ll t[2000042]; void inc(int p) { // increase value at position p for (t[p += n] += 1; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1]; } ll query(int l, int r) { // sum on interval [l, r) ll res = 0; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l&1) res += t[l++]; if (r&1) res += t[--r]; } return res; } map<ll,ll> sizes; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int myId = 0; //// myId = MyNodeId(); //// ll N = 0; //// //cin >> N; N = GetN(); //// ll myConfl = 0; for (int i=min(N - 1, (myId+1) * 1000000LL - 1); i >= myId * 1000000LL; i--) { ll el; //// //cin >> el; el = GetElement(i); //// myConfl += query(1, el); inc(el); if (sizes.size() <= 900) { sizes[el]++; } } if (myId < 99) // recive { Receive(myId+1); ll itsConfl = GetLL(myId+1); myConfl += itsConfl; ll k = GetLL(myId+1); for (int i=0; i<k; i++) { ll wzrost = GetLL(myId+1); ll ile = GetLL(myId+1); myConfl += query(wzrost, 1000001)*ile; sizes[wzrost] += ile; } } if (myId > 0) // send { PutLL(myId-1, myConfl); if (sizes.size() <= 900) { PutLL(myId-1, sizes.size()); for (auto el : sizes) { PutLL(myId-1, el.first); PutLL(myId-1, el.second); } } else { PutLL(myId-1, 0); } Send(myId-1); } if (myId == 0) // cout { cout << myConfl; } return 0; } |