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
#include <bits/stdc++.h>
#include "teatr.h"
#include "message.h"
#include <bits/stdc++.h>                                                        
using namespace std;                                                                                                                    
typedef long long ll;                                                           
typedef pair<int, int> Pii;                                                     
typedef vector<Pii> vpii;                                                       
typedef vector<int> vi;                                                         
typedef vector<ll> vll;                                                         
#define pb push_back                                                            
#define fst first                                                               
#define snd second
//int GetN() { return int(1e8); }
//int GetElement(int i) { return (i * 1ll * i) % int(1e6) + 1; }
//int GetElement(int i) { return 1e6; }
int nodes;
int ja;
int n;
void init()
{
	nodes =  NumberOfNodes();
	ja = MyNodeId();
	n = GetN();
}

void wyslij(int x, vll V)
{
	for(ll y : V)
		PutLL(x, y);
	Send(x);
}
vll odbierz(int x, int ile)
{
	vll res;
	Receive(x);
	for(int i = 0; i < ile; ++i)
		res.pb(GetLL(x));
	return res;
}
const int base = 1 << 20;
int drzewo[2 * base + 100];
void add(int x)
{
	x += base;
	while(x)
	{
		++drzewo[x];
		x >>= 1;
	}
}
int query(int a, int b)
{
	a += base;
	b += base;
	int res = drzewo[a] + drzewo[b];
	while((a >> 1) != (b >> 1))
	{
		if(!(a & 1))
			res += drzewo[a+1];
		if(b & 1)
			res += drzewo[b-1];
			
		a >>= 1;
		b >>= 1;
	}
	return res;
}
int main()
{
	init();
	ll res = 0;
	ll b = 1ll * ja * n / nodes;
	ll e = 1ll * (ja + 1) * n / nodes;
	
	for(int i = 0; i < b; ++i)
		++drzewo[base + GetElement(i)];
	
	for(int i = base - 1; i > 0; --i)
	{
		int l = i * 2;
		int r = l + 1;
		drzewo[i] = drzewo[l] + drzewo[r];
	}
	
	for(int i = b; i < e; ++i)
	{
		int val = GetElement(i);
		res += query(val + 1, 1000100);
		add(val);
	}
	
 	if(ja == 0)
	{
		for(int i = 1; i < nodes; ++i)
			res += odbierz(i, 1)[0];
		printf("%lld\n", res);
	}
	else
		wyslij(0, {res});
	
}