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;
}