blob: cea3869be227f44e25a869522da08f51ba778a46 (
plain)
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
|
# Uses python3
import sys
def mergeInversionCount(B, C, D):
count = 0
while len(B) != 0 and len(C) != 0:
b = B[0]
c = C[0]
if b <= c:
D.append(b)
del B[0]
else:
count = count + len(B)
D.append(c)
del C[0]
D.extend(B)
D.extend(C)
return count
def getInversionCount(A, D):
numOfInversions = 0
if len(A) == 1:
D.append(A[0])
return 0
m = int(len(A) / 2)
D1 = []
numOfInversions = numOfInversions + getInversionCount(A[0:m], D1)
D2 = []
numOfInversions = numOfInversions + getInversionCount(A[m:len(A)], D2)
mergeCount = mergeInversionCount(D1, D2, D)
return numOfInversions + mergeCount
if __name__ == '__main__':
input = sys.stdin.read()
n, *a = list(map(int, input.split()))
b = n * [0]
print(getInversionCount(a, b))
|
