#include<bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; #define pb push_back #define mp make_pair #define st first #define nd second #define ll long long #define ld long double #define ull unsigned ll #define pii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> vector<pair<int,int> > podz(ld n,ld po,ld ko){ // wlacznie z poczatkiem i koncem vector<pair<int,int> > vec; for(ld i=0;i<n;i++){ vec.pb(mp(po+(ko-po)*(i/n),po+(ko-po)*((i+1)/n)-1)); } vec[0].st=po; vec[n-1].nd=ko; return vec; } /*int GetN(){ return 5; } int MyNodeId(){ int n; cin >>n; return n; } int tab[5]={5,2,4,4,3}; int GetElement(int i){ return tab[i]; }*/ ll wyn=0; const int base=(1<<20); int drz[base*2]; void ins(int x){ x+=base; while(x!=0){ drz[x]++; x/=2; } } void wiek(int x){ x+=base; while(x!=0){ if(x%2==0){ wyn+=drz[x+1]; } x/=2; } } void licz(int po,int ko){ //cout <<"licz "<<po <<" "<<ko <<"\n"; for(int i=po;i<=ko;i++){ int a=GetElement(i); wiek(a); ins(a); } } ll kub1[1001000]; ll kub2[1001000]; void roz(pair<int,int> pie,pair<int,int> dr){ //cout <<"roz "<<pie.st <<" "<<pie.nd <<" "<<dr.st <<" "<<dr.nd <<"\n"; int i,a; for(i=pie.st;i<=pie.nd;i++){ a=GetElement(i); kub1[a]++; } for(i=dr.st;i<=dr.nd;i++){ a=GetElement(i); kub2[a]++; } ll ilw=0; for(i=1000010;i>=0;i--){ ilw+=kub1[i+1]; wyn+=ilw*kub2[i]; } } int main(){ vector<pair<int,int> > vec,zad; int n=GetN(); int me=MyNodeId(); int l=min(13,n-1); l=max(l,1); vec=podz(l,0,n-1); for(int i=0;i<l;i++){ for(int j=i+1;j<l;j++){ zad.pb(mp(i,j)); } } if(me<l){ licz(vec[me].st,vec[me].nd); } else{ int me2=me-l; if(me2<zad.size()){ roz(vec[zad[me2].st],vec[zad[me2].nd]); } } ll a; if(me+1<100){ Receive(me+1); a=GetLL(me+1); wyn+=a; } if(me==0){ cout <<wyn; return 0; } PutLL(me-1,wyn); Send(me-1); 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 113 114 115 116 117 | #include<bits/stdc++.h> #include "message.h" #include "teatr.h" using namespace std; #define pb push_back #define mp make_pair #define st first #define nd second #define ll long long #define ld long double #define ull unsigned ll #define pii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> vector<pair<int,int> > podz(ld n,ld po,ld ko){ // wlacznie z poczatkiem i koncem vector<pair<int,int> > vec; for(ld i=0;i<n;i++){ vec.pb(mp(po+(ko-po)*(i/n),po+(ko-po)*((i+1)/n)-1)); } vec[0].st=po; vec[n-1].nd=ko; return vec; } /*int GetN(){ return 5; } int MyNodeId(){ int n; cin >>n; return n; } int tab[5]={5,2,4,4,3}; int GetElement(int i){ return tab[i]; }*/ ll wyn=0; const int base=(1<<20); int drz[base*2]; void ins(int x){ x+=base; while(x!=0){ drz[x]++; x/=2; } } void wiek(int x){ x+=base; while(x!=0){ if(x%2==0){ wyn+=drz[x+1]; } x/=2; } } void licz(int po,int ko){ //cout <<"licz "<<po <<" "<<ko <<"\n"; for(int i=po;i<=ko;i++){ int a=GetElement(i); wiek(a); ins(a); } } ll kub1[1001000]; ll kub2[1001000]; void roz(pair<int,int> pie,pair<int,int> dr){ //cout <<"roz "<<pie.st <<" "<<pie.nd <<" "<<dr.st <<" "<<dr.nd <<"\n"; int i,a; for(i=pie.st;i<=pie.nd;i++){ a=GetElement(i); kub1[a]++; } for(i=dr.st;i<=dr.nd;i++){ a=GetElement(i); kub2[a]++; } ll ilw=0; for(i=1000010;i>=0;i--){ ilw+=kub1[i+1]; wyn+=ilw*kub2[i]; } } int main(){ vector<pair<int,int> > vec,zad; int n=GetN(); int me=MyNodeId(); int l=min(13,n-1); l=max(l,1); vec=podz(l,0,n-1); for(int i=0;i<l;i++){ for(int j=i+1;j<l;j++){ zad.pb(mp(i,j)); } } if(me<l){ licz(vec[me].st,vec[me].nd); } else{ int me2=me-l; if(me2<zad.size()){ roz(vec[zad[me2].st],vec[zad[me2].nd]); } } ll a; if(me+1<100){ Receive(me+1); a=GetLL(me+1); wyn+=a; } if(me==0){ cout <<wyn; return 0; } PutLL(me-1,wyn); Send(me-1); return 0; } |