Problem p02928 (python)

Fixed submission:

MOD = 10 **9 +7
 
N, K = [int(v) for v in raw_input().split()]
A = [int(v) for v in raw_input().split()]

inversions = 0
versions = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            inversions += 1
        if A[i] < A[j]:
            versions += 1



#print('Inversions =  {} '.format(inversions))
#print('Versions =  {} '.format(versions))
res = ((K + 1) * K)/2 * inversions + (K * (K-1))/2 * versions
res = res % MOD
print(res)

Buggy submission (verdict: Runtime Error):
class FenwickTree:
    arr = []
    def __init__(self, n):
        self.arr = [0 for _ in range(n + 1)]

    def inc(self, i, val):
        self.private_inc(i + 1, val)

    def sum(self, a, b):
        return self.private_sum(b+1) - self.private_sum(a)

    def private_inc(self, i, val):

        while i < len(self.arr):
            self.arr[i] += val
            i += i & -i

    def private_sum(self, i):
        s = 0
        while i > 0:
            s += self.arr[i]
            i -= i & -i
        return s

MOD = 10 **9 +7
 
N, K = [int(v) for v in raw_input().split()]
A = [int(v) for v in raw_input().split()]
maxA = max(A)
indexInv = [ [] for _ in range(maxA)]
for index, value in enumerate(A):
    indexInv[value-1].append(index)
nbrs = FenwickTree(maxA+1)
dbl = []
inversions = 0
versions = 0
for k in range(maxA):
    for index in indexInv[k]:

        thisInv = nbrs.sum(index, maxA)
        thisVer = nbrs.sum(0, index -1)
        dbl.append((index, thisInv, thisVer))
    #print('Adding doubles ', dbl)
    for val, invV, vers in dbl:
        inversions += invV
        versions += vers
        nbrs.inc(val, 1)
    dbl = []
#print('Inversions =  {} '.format(inversions))
#print('Versions =  {} '.format(versions))
res = ((K + 1) * K)/2 * inversions + (K * (K-1))/2 * versions
res = res % MOD
print(res)

Buggy submission (verdict: Runtime Error):
class FenwickTree:
    arr = []
    def __init__(self, n):
        self.arr = [0 for _ in range(n + 1)]

    def inc(self, i, val):
        self.private_inc(i + 1, val)

    def sum(self, a, b):
        return self.private_sum(b+1) - self.private_sum(a)

    def private_inc(self, i, val):

        while i < len(self.arr):
            self.arr[i] += val
            i += i & -i

    def private_sum(self, i):
        s = 0
        while i > 0:
            s += self.arr[i]
            i -= i & -i
        return s

MOD = 10 **9 +7
 
N, K = [int(v) for v in raw_input().split()]
A = [int(v) for v in raw_input().split()]
indexInv = [ [] for _ in range(N)]
for index, value in enumerate(A):
    indexInv[value-1].append(index)
nbrs = FenwickTree(N)
dbl = []
inversions = 0
versions = 0
for k in range(N):
    for index in indexInv[k]:

        thisInv = nbrs.sum(index, N-1)
        thisVer = nbrs.sum(0, index -1)
        dbl.append((index, thisInv, thisVer))
    #print('Adding doubles ', dbl)
    for val, invV, vers in dbl:
        inversions += invV
        versions += vers
        nbrs.inc(val, 1)
    dbl = []
#print('Inversions =  {} '.format(inversions))
#print('Versions =  {} '.format(versions))
res = ((K + 1) * K)/2 * inversions + (K * (K-1))/2 * versions
res = res % MOD
print(res)