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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include "message.h"
#include "teatr.h"
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

/*
int GetN() { return 100 * 1000 * 1000; }
int GetElement(int i) { 
if (i < 100 * 1000 * 1000 - 3) return 1 + i / 100;
else return 100 * 1000 * 1000 - i;
}
*/

const int MAXH = 1000002;
int counter[MAXH];
int greater_than[MAXH];
const int NUMBERS_IN_INSTANCE = 1e6; 

int N;
int INSTANCE;
int NODES = 100;
int START_ROW;
int END_ROW;
bool LAST_INSTANCE;

inline int get_element(int i) {
    return GetElement(i - 1);
}

// źródło: http://rafal-nowak.blogspot.com/2012/12/drzewo-przedziaowe.html
class CountingTree
{
private:
    typedef unsigned int uint;
    unsigned const int N;
    std::vector<unsigned int> T;
 
    /** oblicza potege liczby 2, ktora przekracza n
        Warunek:  0 <= n <= 2*10^9
     */
    unsigned int UpperPowerOfTwo( const unsigned int n ) const
    {
        unsigned int ans = 1; while ( ans<=n ) ans <<= 1;
        return ans;
    }
 
public:
    CountingTree(unsigned int max) : N( UpperPowerOfTwo(max) ), T(N<<1,0)
    {
        //fprintf(stderr, "Utworzono drzewo licznikowe o rozmiarze = %d, tzn. maxX = %d\n", T.size(), N-1);
    }
 
    /** liczba wszystkich wstawionych punktów */
    unsigned int size() const { return T[1]; }
 
    /** sprawdzanie czy w strukturze nie ma ¿adnych punktów */
    bool empty() const { return size()==0; }
 
    /** dodawanie punktów o wspó³rzêdnej x
        Argumenty:
            cnt : liczba punktów do wstawienia, domyœlna wartoœæ = 1
        Wynik:
            liczba punktów mniejszych od x
    */
    unsigned int insert( unsigned int x , int cnt = 1 )
    {
        unsigned int k = N+x, ans = 0;
        while(k) { T[k] += cnt; if ((k&1)==1) ans += T[k-1]; k >>= 1; }
    }
 
    /** usuwanie punktów o wspó³rzêdnej x
        Argumenty:
            cnt : liczba punktów do usuniêcia, domyœlna wartoœæ = 1
        Wynik:
            liczba punktów mniejszych od x
    */
    unsigned int remove( unsigned int x , int cnt = 1 ) { return insert(x,-cnt); }
 
    /** k-ty element */
    unsigned int select( unsigned int k ) const
    {
        uint r = 1; while( r<N ) { r <<= 1; if ( T[r] < k ) k -= T[r++]; }
        return r-N;
    }
 
    /** liczba punktów równych x */
    unsigned int how_many_equal( unsigned int x ) const 
    { 
        return T[N+x]; 
    }
 
    /** liczba punktów wiêkszych od x */
    unsigned int how_many_greater( unsigned int x ) const
    {
        unsigned int k = N+x, ans = 0;
        while (k>1) { if ((k&1)==0) ans += T[k+1]; k >>= 1; }
        return ans;
    }
 
    /** liczba punktów mniejszych od x */
    unsigned int how_many_less( unsigned int x ) const { return size() - how_many_equal(x) - how_many_greater(x); }
};

int main() {
    N = GetN();
    INSTANCE = MyNodeId();
    START_ROW = INSTANCE * NUMBERS_IN_INSTANCE + 1;
    END_ROW = (INSTANCE + 1) * NUMBERS_IN_INSTANCE;
    if (START_ROW > N) {
        return 0;
    }
    //cout << START_ROW << " " << N << " " << END_ROW << endl;
    if (START_ROW <= N && N <= END_ROW) {
        LAST_INSTANCE = true;
    }
    CountingTree counter_tree = CountingTree(NUMBERS_IN_INSTANCE);
    long long instanceResult = 0;
    for (int i = START_ROW; i <= min(END_ROW, N); ++i) {
        int h = get_element(i);
        counter[h]++;
        instanceResult += counter_tree.how_many_greater(h);
        //cout << "H " << h << "GREATER" << counter_tree.how_many_greater(h) << endl;
        counter_tree.insert(h);
    }
    for (int i = MAXH; i > 0; i--) {
        greater_than[i] = greater_than[i + 1] + counter[i + 1];
    }
    long long nextResult = 0;
    //cout << INSTANCE << LAST_INSTANCE << endl;
    if (!LAST_INSTANCE) {
        for (int i = END_ROW + 1; i <= N; ++i) {
            int h = get_element(i);
            nextResult += greater_than[h];
        }
    }
    
    long long previousResult = 0;
    if (INSTANCE > 0) {
        Receive(INSTANCE - 1);
        previousResult = GetLL(INSTANCE - 1);
    }
    long long finalResult = instanceResult + nextResult + previousResult;

    if (!LAST_INSTANCE) {
        PutLL(INSTANCE + 1, finalResult);
        Send(INSTANCE + 1);
    } else {
        cout << finalResult << endl;
    }
}