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
#include "teatr.h"
#include "message.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int MAX_N = 1e7+1;

int T[MAX_N];
int C[MAX_N];

typedef long long ll;

ll mergeSort(int p, int q){
    
    if(q-p == 0 ){
        return 0;
    }

    ll res = 0;

    ll s = (p+q)/2;

    res += mergeSort(p,s);
    res += mergeSort(s+1,q);

    int p1 = p, s1 = s+1;
    ll potential = 0;
    for(int i=p; i <=q; i++){

       
        if(p1 <=s && s1 <=q ){
           if(T[p1] > T[s1]){
               C[i] = T[s1++];
               potential++;
           
           }else{
               C[i] =T[p1++];
               res+=potential;
           }

        }else if(p1 <=s ){
            C[i] =T[p1++];
            res+=potential;
        
        }else{
            C[i] = T[s1++];
        }

    }

    for(int i=p; i <=q; i++){
        T[i] = C[i];

    }

    return res;

}

int main(){
    
    if(MyNodeId() != 0){
        return 0;
    }

    int n = GetN();

    for(int i=0; i < n; i++){
        T[i] = GetElement(i);

        
    }

    ll res = mergeSort(0, n-1);
    cout << res << endl;

    return 0;
    
}