#include <bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; typedef long long LL; void startowy() { LL sum = 0; int n = GetN(); int ile = NumberOfNodes()-1; int start = 0; for(int i= 0;i<ile; ++i) { int dl = (n+i)/ile; PutInt(i+1,start); start += dl; PutInt(i+1,start); Send(i+1); } //printf("START\n"); for(int i = 0;i<ile; ++i) { int nr = Receive(i+1); sum += GetLL(i+1); //printf("%lld %d\n", sum, nr); } printf("%lld\n", sum); } const int M = 1<<20; int tree[M*2]; void update(int v) { v+=M; tree[v]++; while(v>1) { v/=2; tree[v]++; } } int getSum(int a, int b) { a+=M; b+=M; if(a==b) return tree[a]; int sum = tree[a] + tree[b]; while(a/2 != b/2) { if(a%2 == 0) sum += tree[a+1]; if(b%2==1) sum += tree[b-1]; a/=2; b/=2; } return sum; } void build() { for(int i = M-1;i>0;--i) tree[i] = tree[i+i] + tree[i+i+1]; } void liczacy() { Receive(0); int l =GetInt(0), p = GetInt(0); LL res = 0; //printf("dostaje %d %d\n",l,p); for(int i= 0;i<l; ++i) { int a= GetElement(i); tree[a+M]++; } build(); for(int i = l; i <p; ++i) { int a= GetElement(i); res += getSum(a+1, M-1); //printf("wal %d ile %d\n", a, res); update(a); } PutLL(0,res); Send(0); } int main() { if(MyNodeId() == 0) startowy(); else liczacy(); }
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 113 | #include <bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; typedef long long LL; void startowy() { LL sum = 0; int n = GetN(); int ile = NumberOfNodes()-1; int start = 0; for(int i= 0;i<ile; ++i) { int dl = (n+i)/ile; PutInt(i+1,start); start += dl; PutInt(i+1,start); Send(i+1); } //printf("START\n"); for(int i = 0;i<ile; ++i) { int nr = Receive(i+1); sum += GetLL(i+1); //printf("%lld %d\n", sum, nr); } printf("%lld\n", sum); } const int M = 1<<20; int tree[M*2]; void update(int v) { v+=M; tree[v]++; while(v>1) { v/=2; tree[v]++; } } int getSum(int a, int b) { a+=M; b+=M; if(a==b) return tree[a]; int sum = tree[a] + tree[b]; while(a/2 != b/2) { if(a%2 == 0) sum += tree[a+1]; if(b%2==1) sum += tree[b-1]; a/=2; b/=2; } return sum; } void build() { for(int i = M-1;i>0;--i) tree[i] = tree[i+i] + tree[i+i+1]; } void liczacy() { Receive(0); int l =GetInt(0), p = GetInt(0); LL res = 0; //printf("dostaje %d %d\n",l,p); for(int i= 0;i<l; ++i) { int a= GetElement(i); tree[a+M]++; } build(); for(int i = l; i <p; ++i) { int a= GetElement(i); res += getSum(a+1, M-1); //printf("wal %d ile %d\n", a, res); update(a); } PutLL(0,res); Send(0); } int main() { if(MyNodeId() == 0) startowy(); else liczacy(); } |