Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

The Number of Inversions

  For a given sequence $A = \{a_0, a_1, ... a_{n-1}\}$, the number of pairs $(i, j)$ where $a_i > a_j$ and $i < j$, is called the number of inversions. The number of inversions is equal to the number of swaps of Bubble Sort defined in the following program:

bubbleSort(A)
  cnt = 0 // the number of inversions
  for i = 0 to A.length-1
    for j = A.length-1 downto i+1
      if A[j] < A[j-1]
	swap(A[j], A[j-1])
	cnt++

  return cnt

  For the given sequence $A$, print the number of inversions of $A$. Note that you should not use the above program, which brings Time Limit Exceeded.

Input

  In the first line, an integer $n$, the number of elements in $A$, is given. In the second line, the elements $a_i$ ($i = 0, 1, .. n-1$) are given separated by space characters.

output

  Print the number of inversions in a line.

Constraints

$ 1 \leq n \leq 200,000$

$ 0 \leq a_i \leq 10^9$

$a_i$ are all different

Sample Input 1

5
3 5 2 1 4

Sample Output 1

6

Sample Input 2

3
3 1 2

Sample Output 2

2



Sample input:
5
3 5 2 1 4


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
import sys

sintinel = 1000000001

def merge_sort(A, l, r):
    if l + 1 < r:
        mid = (l + r) // 2
        merge_sort(A, l, mid)
        merge_sort(A, mid, r)
        merge(A, l, mid, r)

def merge(A, l, mid, r):
    global count
    for j in range(mid, r):
        y = j
        x = y - 1
        while l <= x and A[y] < A[x]:
            count += 1
            tmp = A[y]
            A[y] = A[x]
            A[x] = tmp
            y -= 1
            x -= 1

count = 0
n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

merge_sort(A, 0, n)
print(count)

Submission status: Time Limit Exceeded

Solution code:
#coding:UTF-8
def NI(A):
    cnt=0
    for i in range(len(A)):
        for j in reversed(range(i+1,len(A))):
            if A[j]<A[j-1]:
                swap=A[j]
                A[j]=A[j-1]
                A[j-1]=swap
                cnt+=1
    print(cnt)
    
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    NI(A)

Submission status: Time Limit Exceeded

Solution code:
def bubble_sort_revision(target_list):

    list_length = len(target_list)
    
    flag = True
    change_count = 0
    top_index = 1
    while flag:
        flag = False
        for i in range(top_index, list_length)[::-1]:
            if target_list[i] < target_list[i - 1]:
                tmp = target_list[i]
                target_list[i] = target_list[i - 1]
                target_list[i - 1] = tmp
                change_count += 1
                flag = True
        top_index += 1

    return change_count
if __name__ == "__main__":
    l = input()
    target_list = [int(i) for i in input().split()]
    print(bubble_sort_revision(target_list))

Submission status: Time Limit Exceeded

Solution code:
def bubble_sort_revision(target_list):

    list_length = len(target_list)
    
    flag = True
    change_count = 0
    for top_index in range(1,list_length):
        for i in range(top_index, list_length)[::-1]:
            if target_list[i] < target_list[i - 1] and target_list[top_index] >= target_list[i]:
                tmp = target_list[i]
                target_list[i] = target_list[i - 1]
                target_list[i - 1] = tmp
                change_count += 1
    return change_count
if __name__ == "__main__":
    l = input()
    target_list = [int(i) for i in input().split()]
    print(bubble_sort_revision(target_list))

Submission status: Time Limit Exceeded

Solution code:
def bubble_sort_revision(target_list):

    list_length = len(target_list)
    
    flag = True
    change_count = 0
    
    for top_index in range(1,list_length):
        for i in range(top_index, list_length)[::-1]:
            if target_list[i] < target_list[i - 1] and target_list[top_index] >= target_list[i]:
                tmp = target_list[i]
                target_list[i] = target_list[i - 1]
                target_list[i - 1] = tmp
                change_count += 1
                
    return change_count
def solve(n, target_list):
    a = [0 for i in range(max(target_list) + 1)]
    ans = 0
    for i in range(n):
        ans += i - sum(a[:target_list[i]])
        a[target_list[i]] += 1
    return ans

if __name__ == "__main__":
    l = int(input())
    target_list = [int(i) for i in input().split()]
    print(solve(l, target_list))

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self,n):
        self.bit = [0 for i in range(n + 1)]
        self.n = n

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += int(bin(i & -i), 2)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= int(bin(i & -i), 2)
        return s

def solve(n, target_list):
    bit = Bit(max(target_list))
    ans = 0
    for i in range(n):
        ans += i - bit.sum(target_list[i])
        bit.add(target_list[i],1)
    return ans

if __name__ == "__main__":
    l = int(input())
    target_list = [int(i) for i in input().split()]
    print(solve(l, target_list))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))

cnt = 0
for i in range(len(A) - 1):
  for j in range(i + 1, len(A)):
    if A[i] > A[j]: cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def bubbleSort(A):
    count = 0
    for i in range(len(A)):
        for j in range(i+1,len(A))[::-1]:
            if A[j] < A[j-1]:
                ret = A[j]
                A[j] = A[j-1]
                A[j-1] = ret
                count +=1
    return count 
input()
print(bubbleSort(list(map(int,input().split()))))

Submission status: Time Limit Exceeded

Solution code:
# O(n^2)
n = raw_input()                                                
l = map(int, raw_input().split())                              
                                                               
sum = 0                                                        
for i in xrange(len(l)):                                       
    for j in xrange(i+1, len(l)):                              
        if l[i] > l[j]: sum += 1                               
print sum

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
cnt = 0

for i in range(n):
    for j in range(i+1, n):
        if A[i] > A[j]:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def insertion(A):
  count = 0
  for i in range(1, len(A)):
    for j in range(i, 0, -1):
      if A[j] < A[j-1]:
        A[j], A[j-1] = A[j-1], A[j]
        count += 1
      else:
        break
  return count

def main():
  n = int(input())
  A = list(map(int, input().split()))
  print(insertion(A))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def main():
    """ ????????? """
    num = int(input().strip())
    A = list(map(int,input().split()))
    cnt = 0
    for i in range(num-1):
        for j in range(i,num):
            if A[i] > A[j]:
                cnt+= 1

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
flag = 1
count = 0
while flag:
    flag = 0
    for i in range(n-1):
        if a[i] > a[i+1]:
            a[i], a[i+1] = a[i+1], a[i]
            count += 1
            flag = 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())

cnt = 0
for i in xrange(n):
	for j in xrange(i+1,n):
		if A[i] > A[j]:
			cnt += 1
print cnt

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    reverse = 0
    for i in range(len(a)):
        reverse += sum(1 for x in a[i+1:] if x < a[i])
    print(reverse)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
# coding=utf-8


def merge(al2: list, left: int, middle: int, right: int) -> int:
    n1 = middle - left
    n2 = right - middle

    left_list = [al2[left + i] for i in range(n1)]
    right_list = [al2[middle + i] for i in range(n2)]
    left_list.append(1000000007)
    right_list.append(1000000007)

    i = 0
    j = 0
    ctr = 0
    for k in range(left, right):
        if left_list[i] <= right_list[j]:
            al2[k] = left_list[i]
            i += 1
        else:
            ctr += len(left_list[i:])-1
            al2[k] = right_list[j]
            j += 1
    return ctr


def merge_sort(al: list, left: int, right: int, counter: int) -> (list, int):
    if left+1 < right:
        mid = (left + right)//2
        counter1 = merge_sort(al, left, mid, counter)[1]
        counter2 = merge_sort(al, mid, right, counter)[1]
        counter += merge(al, left, mid, right)
        counter += counter1
        counter += counter2
    return al, counter


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    reverse_counter = 0
    a, reverse_counter = merge_sort(a[:], 0, len(a), reverse_counter)
    print(reverse_counter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if A[i] > A[j]:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
print(sum(A[i] > A[j] for i in range(N - 1) for j in range(i + 1, N)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
print(sum(1 for i in range(N - 1) for j in range(i + 1, N) if A[i] > A[j]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
A = tuple(map(int, input().split()))
print(sum(1 for i, j in combinations(range(N), 2) if A[i] > A[j]))

Submission status: Time Limit Exceeded

Solution code:
count = int(input());
data = [int(n) for n in input().split()];

def number_of_inversions():
    ans = 0;
    for i in range(count):
        value = data[i];
        for j in range(i + 1, count):
            if data[j] < value:
                ans += 1;
    return ans;

print(number_of_inversions());

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def bubble_sort(A):
    swap_count = 0
    for i in range(len(A)-1):
        for x in range(i, len(A)):
            if A[x] < A[i]:
                swap_count += 1
                # A[x], A[x-1] = A[x-1], A[x]

    return swap_count

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

swap_count = bubble_sort(A)
print(swap_count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
    for k in range(i+1, n):
        if a[i] > a[k]:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

def bscount(nums):
    """count the number of inversions (ai > aj and i < j)
    in a sequence of ints num.

    Count number of inversions using sorted list of 0..k

    >>> bscount([3, 5, 2, 1, 4])
    6
    >>> bscount([10, 2, 9, 4, 6, 5, 7, 8, 3, 1])
    29
    """
    def binsearch(li, n, e):
        i, j = 0, n-1
        while i <= j:
            mid = (i + j) // 2
            if li[mid] > e:
                j = mid - 1
            elif li[mid] < e:
                i = mid + 1
            else:
                i = mid
                break
        return i

    snums = []
    length = 0
    invs = 0

    for n in nums:
        i = binsearch(snums, length, n)
        invs += length - i
        snums.insert(i, n)
        length += 1

    return invs


def run():
    _ = int(input())  # flake8: noqa
    nums = [int(i) for i in input().split()]

    print(bscount(nums))


if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:

def bscount(nums):
    """count the number of inversions (ai > aj and i < j)
    in a sequence of ints num.

    Count number of inversions using sorted list of 0..k

    >>> bscount([3, 5, 2, 1, 4])
    6
    >>> bscount([10, 2, 9, 4, 6, 5, 7, 8, 3, 1])
    29
    """
    def binsearch(li, n, e):
        i, j = 0, n-1
        while i <= j:
            mid = (i + j) // 2
            if li[mid] > e:
                j = mid - 1
            elif li[mid] < e:
                i = mid + 1
            else:
                i = mid
                break
        return i

    snums = []
    length = 0
    invs = 0

    for n in nums:
        i = binsearch(snums, length, n)
        invs += length - i
        snums.insert(i, n)
        length += 1

    return invs


def run():
    _ = int(input())  # flake8: noqa
    nums = [int(i) for i in input().split()]

    print(bscount(nums))


if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
number = int(input())
text = [int(x.strip()) for x in input().split()]

cnt = 0
for i in range(number):
    for j in range(i+1,number):
        if text[i] > text[j]:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def bubble(array):
    cnt = 0
    for i in range(len(array)):
        for j in range(len(array) - 1, i, -1):
            if array[j] < array[j-1]:
                array[j], array[j-1] = array[j-1], array[j]
                cnt += 1
    return cnt


n = int(input())
array = [int(x) for x in input().split()]

print(bubble(array))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
array = [int(x) for x in input().split()]

cnt = 0
for i in range(n):
    for j in range(n-1, i, -1):
        if array[i] > array[j]:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def bubble(A):
    #标记是否需要继续冒泡
    flag =True;
    n=len(A)
    i=0
    cnt=0
    while flag:
        flag=False
        for j in range(n-1,i,-1):
           if A[j]<A[j-1]:
               A[j],A[j-1]=A[j-1],A[j]
               flag=True
               cnt+=1
        i+=1
    return cnt    

n=int(input())
A=[int(x) for x in input().split()]  
rt=bubble(A)
print(rt)

Submission status: Time Limit Exceeded

Solution code:
def bubbleSort(A):
	cnt=0
	for i in range(len(A)):
		for j in range(len(A)-1,i,-1):
			if A[j]<A[j-1]:
				A[j],A[j-1]=A[j-1],A[j]
				cnt+=1
	return cnt

n=int(input())
A=list(map(int,input().split()))
print(bubbleSort(A))

Submission status: Time Limit Exceeded

Solution code:
def shakerSort(A):
	cnt=0
	left=0
	sh=0
	right=len(A)-1
	while left<right:
		for i in range(left,right):
			if A[i]>A[i+1]:
				A[i],A[i+1]=A[i+1],A[i]
				sh=i
				cnt+=1
		right=sh
		for j in range(right,left,-1):
			if A[j]<A[j-1]:
				A[j],A[j-1]=A[j-1],A[j]
				sh=j
				cnt+=1
		left=sh
	return cnt

n=int(input())
A=list(map(int,input().split()))
print(shakerSort(A))

Submission status: Time Limit Exceeded

Solution code:
def bubble_sort(ary):
    flag = True
    cnt = 0
    i = 0
    while flag:
        flag = False
        for j in range(len(ary) - 1, i, -1):
            if ary[j] < ary[j - 1]:
                ary[j], ary[j - 1] = ary[j - 1], ary[j]
                flag = True
                cnt += 1
        i += 1

    # for i in range(0, len(ary) - 1):
    #     for j in range(len(ary) - 1, i, -1):
    #         if ary[j] < ary[j - 1]:
    #             ary[j], ary[j - 1] = ary[j - 1], ary[j]
    #             cnt += 1

    return cnt


n = int(input())
ary = [int(_) for _ in input().split()]
print(bubble_sort(ary))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(e) for e in input().split()]
cnt = 0
for i in range(n-1):
    for j in range(n-1, i, -1):
        if a[j] < a[j-1]:
            w = a[j]; a[j] = a[j-1]; a[j-1] = w
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().strip().split()))

count = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[j] < a[i]: count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().strip().split()))

count = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[j] < a[i]: count += 1
print(count)

Submission status: Memory Limit Exceeded

Solution code:
def num_of_inversions(A, n, cnt = 0):
    """Return the number of inversions in the sequence A.

    A is a list of numbers.
    n is the length of A.
    cnt is a accumulator.
    """

    if n == 1:
        return cnt
    flag = 1
    t_cnt = 0
    t_lt = A[-1]
    for i in reversed(A[:n - 1]):
        if i > t_lt:
            t_cnt += 1
            
    return num_of_inversions(A[:n - 1], n - 1, cnt + t_cnt)


import sys

sys.setrecursionlimit(100000)

n = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))

ans = num_of_inversions(A, n)

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
def bubble_sort_revision(target_list):

    list_length = len(target_list)
    
    flag = True
    change_count = 0
    
    for top_index in range(1,list_length):
        for i in range(top_index, list_length)[::-1]:
            if target_list[i] < target_list[i - 1] and target_list[top_index] >= target_list[i]:
                tmp = target_list[i]
                target_list[i] = target_list[i - 1]
                target_list[i - 1] = tmp
                change_count += 1
                
    return change_count

def my_add(bit, i, x):
    while i <= len(bit) - 1:
        bit[i] += x
        i += int(bin(i & -i), 2)
        
def my_sum(bit, i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= int(bin(i & -i), 2)
    return s

def solve(n, target_list):
    bit = [0 for i in range(max(target_list) + 2)]
    ans = 0
    for i in range(n):
        ans += i - my_sum(bit, target_list[i] + 1)
        my_add(bit, target_list[i] + 1, 1)
    return ans

if __name__ == "__main__":
    l = int(input())
    target_list = [int(i) for i in input().split()]
    print(solve(l, target_list))

Submission status: Accepted

Solution code:
import sys
cnt = 0

def merge_sort(a, left, right):
	if left + 1 < right:
		mid = int(left + (right - left) / 2)
		merge_sort(a, left, mid)
		merge_sort(a, mid, right)
		merge(a, left, mid, right)

def merge(a, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L = a[left:left+n1]
	R = a[mid:mid+n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)
	i = j = 0
	tmp = n1
	for k in range(left, right):
		if L[i] <= R[j]:
			if R[j] != sys.maxsize:
				tmp -= 1
			a[k] = L[i]
			i += 1
		else:
			if L[i] != sys.maxsize:
				global cnt
				cnt += tmp
			a[k] = R[j]
			j += 1		
	
n = int(input())
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)

Submission status: Accepted

Solution code:
import sys
cnt = 0

def merge_sort(a, left, right):
	if left + 1 < right:
		mid = int(left + (right - left) / 2)
		merge_sort(a, left, mid)
		merge_sort(a, mid, right)
		merge(a, left, mid, right)

def merge(a, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L = a[left:left + n1]
	R = a[mid:mid + n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)
	i = j = 0
	for k in range(left, right):
		if L[i] <= R[j]:
			a[k] = L[i]
			i += 1
		else:
			if L[i] != sys.maxsize:
				global cnt
				cnt += n1 - i
			a[k] = R[j]
			j += 1

n = int(input())
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)

Submission status: Accepted

Solution code:
import sys
cnt = 0

def merge_sort(a, left, right):
	if left + 1 < right:
		mid = int(left + (right - left) / 2)
		merge_sort(a, left, mid)
		merge_sort(a, mid, right)
		merge(a, left, mid, right)

def merge(a, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L = a[left:left+n1]
	R = a[mid:mid+n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)
	i = j = 0
	for k in range(left, right):
		if L[i] <= R[j]:
			a[k] = L[i]
			i += 1
		else:
			if i < n1:
				global cnt
				cnt += n1 - i
			a[k] = R[j]
			j += 1
	
n = int(input())
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.bit = [0]*(n+1)
    
    def sumB(self, i):
        s = 0
        while(i>0):
            s+=self.bit[i]
            i -= i & -i
        return s
    
    def addB(self, i, x):
        while(i < len(self.bit)):
            self.bit[i] += x
            i += i & -i
            
n = int(input())
A = [(i+1,int(j)) for i,j in enumerate(input().split())]
A = sorted(A, key=lambda x: x[1])
b = BIT(n)
for i in range(n):b.addB(i+1,1)
ans=0
for i,j in A:
    ans+=b.sumB(i)
    b.addB(i,-1)
print(ans-n)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.bit = [0]*(n+1)
    
    def sumB(self, i):
        s = 0
        while(i>0):
            s+=self.bit[i]
            i -= i & -i
        return s
    
    def addB(self, i, x):
        while(i < len(self.bit)):
            self.bit[i] += x
            i += i & -i
            
n = int(input())
A = [(i+1,int(j)) for i,j in enumerate(input().split())]
A = sorted(A, key=lambda x: x[1])
b = BIT(n)
for i in range(n):b.addB(i+1,1)
ans=0
for i,j in A:
    ans+=b.sumB(i-1)
    b.addB(i,-1)
print(ans)

Submission status: Accepted

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from math import inf

inv = 0


def merge(A, left, mid, right):
    global inv

    L = A[left:mid]
    L.append(inf)
    R = A[mid:right]
    R.append(inf)
    i = j = 0
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            inv += len(L) - i - 1
            A[k] = R[j]
            j += 1


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    merge_sort(A, 0, n)
    print(inv)


main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

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

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N)

A_sorted = {a: i for i, a in enumerate(sorted(A), start=1)}
ans = 0
for j, a in enumerate(A):
    ans += j - BIT.sum(A_sorted[a])
    BIT.add(A_sorted[a], 1)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [(i + 1, int(j)) for i, j in enumerate(input().split())]
A.sort(key=lambda x: -x[1])

class BIT:
    def __init__(self, n):
        self.data = [0] * (n + 1)
    def add(self, i, x):
        while i <= n:
            self.data[i] += x
            # 区間の長さ
            i += i & -i

    def get(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s

b = BIT(n)
ans = 0
for i, j in A:
    ans += b.get(i)
    b.add(i, 1)
print(ans)

Submission status: Accepted

Solution code:
import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
def dump(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

# 5
# 3 5 2 1 4
def cum(i):
    res = 0
    while i>0:
        res += bit[i]
        i -= i&-i
    return res

def add(i, x):
    while i<=N:
        bit[i] += x
        i += i&-i

def pos(a):
    return i

def solve():
    global N,A,bit
    N = int(input())
    A = list(map(int, input().split()))
    bit = [0]*(N+1)

    B = list(set(A))
    B.sort()
    B = [-1] + B

    res = 0
    for i in range(N):
        j = bisect_left(B, A[i])
        res += cum(j)
        add(j, 1)

    print(N*(N-1)//2-res)

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
    except:
        pass
    solve()
# vim: set foldmethod=marker:}}}

Submission status: Accepted

Solution code:
import sys
time_check = False
if time_check:
    import time

num_of_inversions = 0
array = [0 for x in range(200000)]

def merge(left, mid, right):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = array[left:left + n_fore]
    l_fore.append(sys.maxsize)
    l_rear = array[mid:mid + n_rear]
    l_rear.append(sys.maxsize)

    i = j = 0
    global num_of_inversions

    offset = len(l_fore) - 1 + left
    for k in range(left, right):
        if l_fore[i] < l_rear[j]:
            array[k] = l_fore[i]
            i += 1
        else:
            array[k] = l_rear[j]
            num_of_inversions += j - k + offset
            #print(l_fore,l_rear, array[:23])
            #print(num_of_inversions,len(l_fore),len(l_rear),i,j,k)
            j += 1


def merge_sort(left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)
    return


def main():

    n = int(input())
    for idx, value in enumerate(input().split()):
        array[idx] = int(value)

    if time_check:
        start = time.time()

    merge_sort(0, n)

    if time_check:
        print("elapsed_time:", time.time() - start)

    #print(" ".join(map(str, array[:n])))
    print(num_of_inversions)

    return


main()

Submission status: Accepted

Solution code:
def InputData():
    
    sequence_len = int(input())
    sequence = [int(a) for a in input().split(" ")]

    return sequence_len, sequence

def bubbleSort(A):
    cnt = 0
    for i in range(len(A)-1):
        for j in range(len(A)-1, i+1, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    
    return cnt

def merge(sequence, left, mid, right):
    global merge_cnt
    n1 = mid - left
    n2 = right - mid
    sequence_left = sequence[left:left + n1]
    sequence_right = sequence[mid:mid + n2]
    sequence_left.append(float('inf'))
    sequence_right.append(float('inf'))

    left_cnt = 0
    right_cnt = 0
    for i in range(left, right):
        if sequence_left[left_cnt] <= sequence_right[right_cnt]:
            # print(sequence_left[left_cnt])
            sequence[i] = sequence_left[left_cnt]
            left_cnt += 1
        else:
            # print(sequence_right[right_cnt])
            sequence[i] = sequence_right[right_cnt]
            right_cnt += 1
            merge_cnt += n1 - left_cnt

def mergeSort(sequence, left, right):
    if left + 1 < right:
        # print(merge_cnt)
        mid = (left + right) // 2
        mergeSort(sequence, left, mid)
        mergeSort(sequence, mid, right)
        merge(sequence, left, mid, right)

def PrintOut(cnt):
    print(cnt)

def main():
    [sequence_len, sequence] = InputData()
    # cnt = bubbleSort(sequence)
    global merge_cnt
    merge_cnt = 0
    mergeSort(sequence, 0, sequence_len)
    PrintOut(merge_cnt)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
INF = float('inf')

def merge(lst,left,middle,right):
    cnt = 0
    left_lst  =  lst[left:middle] + [INF]
    right_lst = lst[middle:right] + [INF]

    i,j = 0,0
    for k in range(left,right):
        if left_lst[i] <= right_lst[j]:
            lst[k] = left_lst[i]
            i += 1
        else:
            lst[k] = right_lst[j]
            j += 1
            cnt += (len(left_lst)-1) - i
    return cnt

def merge_sort(lst,left,right):
    if left+1 < right:
        middle = (left+right)//2
        a = merge_sort(lst,left,middle)
        b = merge_sort(lst,middle,right)
        c = merge(lst,left,middle,right)
        return a+b+c
    return 0

n = int(input())
n_lst = list(map(int,input().split()))
ans = merge_sort(n_lst,0,n)
print(ans)

Submission status: Accepted

Solution code:
INF=1000000005
def merge(a,right,mid,left):
    r=a[right:mid]
    l=a[mid:left]
    i=0
    j=0
    q=mid-right
    r.append(INF)
    l.append(INF)
    cnt=0
    while i+j!=left-right:
        if r[i]>l[j]:
            a[right+i+j]=l[j]
            j+=1
            cnt+=q-i
        else:
            a[right+i+j]=r[i]
            i+=1
    return cnt
def mergesort(a,right,left):
    if right+1<left:
        mid=(right+left)//2
        v1=mergesort(a,right,mid)
        v2=mergesort(a,mid,left)
        v3=merge(a,right,mid,left)
        return v1+v2+v3
    else:
        return 0
n=int(input())
a=list(map(int,input().split()))
ans=mergesort(a,0,n)
print(ans)

Submission status: Accepted

Solution code:
#marge sort マージソート ＋　転倒数
n = int(input())
a = list(map(int, input().split()))
cnt = 0

def marge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [0]*(n1+1) 
    R = [0]*(n2+1)
    #L[0,,,,,n1]とr[0,,,,n2]を生成
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = pow(10,10)
    R[n2] = pow(10,10)
    
    l = 0
    r = 0
    for k in range(left, right):
        if L[l] <= R[r]:
            A[k] = L[l]
            l += 1
        else:
            A[k] = R[r]
            r += 1
            cnt += n1 - l

def margeSort(A, left, right):
    if 2 <= right - left:
        mid = (left + right)//2
        margeSort(A, left, mid)
        margeSort(A, mid, right)
        marge(A, left, mid, right)
    
        
margeSort(a, 0, len(a))
print(cnt)