#include<bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; #define st first #define nd second #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) typedef long long lli; typedef pair<int, int> pii; typedef pair<lli, lli> pll; typedef pair<lli, int> pli; typedef pair<int, lli> pil; const int N=4e6+9, pot=1<<20, X=8e6; int drzewo[N]; lli wyn=0; void wstaw(int v, int x) { drzewo[v]+=x; if(v==1)return; wstaw(v/2, x); } int oblicz(int v, int a, int b, int x) { if(b<x)return 0; if(a>=x)return drzewo[v]; int akt=(a+b)/2; return oblicz(2*v, a, akt, x)+oblicz(2*v+1, akt+1, b, x); } int main() { int nr=MyNodeId(), n=GetN(); if(nr<13) { int pocz=nr*X, kon=min(n, (nr+1)*X); for(int i=pocz;i<kon;i++) { int k=GetElement(i); wyn+=oblicz(1, 1, pot, k+1); wstaw(pot+k-1, 1); } PutLL(91, wyn); Send(91); } else if(nr<91) { int pocz1=12, blep=91, pom=1; while(blep>nr) { blep-=pom; pom++; pocz1--; } int pocz2=(nr-blep+pocz1+1)*X; pocz1*=X; int kon1=min(n, pocz1+X), kon2=min(n, pocz2+X); for(int i=pocz1;i<kon1;i++)drzewo[GetElement(i)+pot-1]++; for(int i=0;i<pot;i+=2)wstaw((pot+i)/2, drzewo[pot+i]+drzewo[pot+i+1]); for(int i=pocz2;i<kon2;i++) { int k=GetElement(i); wyn+=oblicz(1, 1, pot, k+1); } PutLL(91, wyn); Send(91); } else if(nr==91) { lli global=0; for(int i=90;i>=0;i--) { Receive(i); global+=GetLL(i); } cout<<global<<"\n"; } 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<bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; #define st first #define nd second #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) typedef long long lli; typedef pair<int, int> pii; typedef pair<lli, lli> pll; typedef pair<lli, int> pli; typedef pair<int, lli> pil; const int N=4e6+9, pot=1<<20, X=8e6; int drzewo[N]; lli wyn=0; void wstaw(int v, int x) { drzewo[v]+=x; if(v==1)return; wstaw(v/2, x); } int oblicz(int v, int a, int b, int x) { if(b<x)return 0; if(a>=x)return drzewo[v]; int akt=(a+b)/2; return oblicz(2*v, a, akt, x)+oblicz(2*v+1, akt+1, b, x); } int main() { int nr=MyNodeId(), n=GetN(); if(nr<13) { int pocz=nr*X, kon=min(n, (nr+1)*X); for(int i=pocz;i<kon;i++) { int k=GetElement(i); wyn+=oblicz(1, 1, pot, k+1); wstaw(pot+k-1, 1); } PutLL(91, wyn); Send(91); } else if(nr<91) { int pocz1=12, blep=91, pom=1; while(blep>nr) { blep-=pom; pom++; pocz1--; } int pocz2=(nr-blep+pocz1+1)*X; pocz1*=X; int kon1=min(n, pocz1+X), kon2=min(n, pocz2+X); for(int i=pocz1;i<kon1;i++)drzewo[GetElement(i)+pot-1]++; for(int i=0;i<pot;i+=2)wstaw((pot+i)/2, drzewo[pot+i]+drzewo[pot+i+1]); for(int i=pocz2;i<kon2;i++) { int k=GetElement(i); wyn+=oblicz(1, 1, pot, k+1); } PutLL(91, wyn); Send(91); } else if(nr==91) { lli global=0; for(int i=90;i>=0;i--) { Receive(i); global+=GetLL(i); } cout<<global<<"\n"; } return 0; } |