Problem:


Score : 600 points

Problem Statement

There are 2N balls, N white and N black, arranged in a row. The integers from 1 through N are written on the white balls, one on each ball, and they are also written on the black balls, one on each ball.
The integer written on the i-th ball from the left (1 ≤ i ≤ 2N) is a_i, and the color of this ball is represented by a letter c_i.
c_i = W represents the ball is white; c_i = B represents the ball is black.

Takahashi the human wants to achieve the following objective:

For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the white ball with i written on it is to the left of the white ball with j written on it.

For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the black ball with i written on it is to the left of the black ball with j written on it.

In order to achieve this, he can perform the following operation:

Swap two adjacent balls.

Find the minimum number of operations required to achieve the objective.

Constraints

1 ≤ N ≤ 2000

1 ≤ a_i ≤ N

c_i = W or c_i = B.

If i ≠ j, (a_i,c_i) ≠ (a_j,c_j).

Input

Input is given from Standard Input in the following format:

N
c_1 a_1
c_2 a_2
:
c_{2N} a_{2N}

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

3
B 1
W 2
B 3
W 1
W 3
B 2

Sample Output 1

4

The objective can be achieved in four operations, for example, as follows:

Swap the black 3 and white 1.

Swap the white 1 and white 2.

Swap the black 3 and white 3.

Swap the black 3 and black 2.

Sample Input 2

4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1

Sample Output 2

18

Sample Input 3

9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7

Sample Output 3

41



Sample input:
3
B 1
W 2
B 3
W 1
W 3
B 2


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


# 解説
N = int(sys.stdin.buffer.readline())
CA = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(N * 2)]
C = []
A = []
for c, a in CA:
    C.append(c)
    A.append(int(a))

pos_w = [IINF] * (N + 1)
pos_b = [IINF] * (N + 1)
for i, (c, a) in enumerate(list(zip(C, A))):
    if c == 'W':
        pos_w[a] = i
    else:
        pos_b[a] = i

# count_b[k][i]: i より左に、k 以下の黒が何個あるか
# count_w[k][i]: i より左に、k 以下の白が何個あるか
bc = [0] * (N * 2 + 1)
wc = [0] * (N * 2 + 1)
count_b = [[0] * (N * 2 + 1)]
count_w = [[0] * (N * 2 + 1)]
for k in range(1, N + 1):
    wc[pos_w[k] + 1] = 1
    bc[pos_b[k] + 1] = 1
    count_b.append(cumsum(bc))
    count_w.append(cumsum(wc))

# dp[b][w]: B を b 回、W を w 回使ったときの転倒数の最小値
dp = [[INF] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N * 2):
    b = i
    w = 0
    if b > N:
        w = b - N
        b -= w

    while w <= min(i, N):
        if b < N:
            # b + 1 を使う。
            # 位置の写像が与えられたときのスワップの回数だから転倒数
            # もともといた位置より右にあったやつで、既に使ってるのが何個か
            orig_pos = pos_b[b + 1]
            inv = i - count_b[b + 1][orig_pos] - count_w[w][orig_pos]
            dp[b + 1][w] = min(dp[b + 1][w], dp[b][w] + inv)
        if w < N:
            orig_pos = pos_w[w + 1]
            inv = i - count_b[b][orig_pos] - count_w[w + 1][orig_pos]
            dp[b][w + 1] = min(dp[b][w + 1], dp[b][w] + inv)
        b -= 1
        w += 1
print(dp[N][N])

# import numpy as np
#
# print(np.array(dp))

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size

    def copy(self):
        ret = BinaryIndexedTree(0)
        ret._bit = self._bit[:]
        ret._size = self._size
        return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


N = int(sys.stdin.buffer.readline())
CA = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(N * 2)]
C = []
A = []
for c, a in CA:
    a = int(a) - 1
    C.append(c)
    A.append(a)

pos_w = [-1] * N
pos_b = [-1] * N
ca = []
for i, (c, a) in enumerate(list(zip(C, A))):
    if c == 'W':
        pos_w[a] = i
    else:
        pos_b[a] = i

# dp[b][w]: 今までに B を b 個、W を w 個使ったときの答えの最小値
dp = [[INF] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
bits = [[None] * (N + 1) for _ in range(N + 1)]
bits[0][0] = BinaryIndexedTree(size=N * 2)
for i, (c, a) in enumerate(list(zip(C, A))):
    b = max(0, i - N)
    w = min(i, N)
    while w >= max(0, i - N):
        #: :type: BinaryIndexedTree
        bit = bits[b][w]
        if b < N:
            inv = i - bit.sum(pos_b[b])
            dp[b + 1][w] = min(dp[b + 1][w], dp[b][w] + inv)
        if w < N:
            inv = i - bit.sum(pos_w[w])
            dp[b][w + 1] = min(dp[b][w + 1], dp[b][w] + inv)

        c = 0
        c += b < N and not bits[b + 1][w]
        c += w < N and not bits[b][w + 1]
        if b < N and not bits[b + 1][w]:
            bits[b + 1][w] = bit.copy() if c == 2 else bit
            bits[b + 1][w].add(pos_b[b], 1)
            ref = False
        if w < N and not bits[b][w + 1]:
            bits[b][w + 1] = bit
            bits[b][w + 1].add(pos_w[w], 1)
            ref = False
        b += 1
        w -= 1
    # import numpy as np
    # print(np.array(dp))
    # print()
print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size

    def copy(self):
        ret = BinaryIndexedTree(0)
        ret._bit = self._bit[:]
        ret._size = self._size
        return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


N = int(sys.stdin.buffer.readline())
CA = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(N * 2)]
C = []
A = []
for c, a in CA:
    a = int(a) - 1
    C.append(c)
    A.append(a)

pos_w = [-1] * N
pos_b = [-1] * N
ca = []
for i, (c, a) in enumerate(list(zip(C, A))):
    if c == 'W':
        pos_w[a] = i
    else:
        pos_b[a] = i

# dp[b][w]: 今までに B を b 個、W を w 個使ったときの答えの最小値
dp = [[INF] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
bits = [[None] * (N + 1) for _ in range(N + 1)]
bits[0][0] = BinaryIndexedTree(size=N * 2)
for i, (c, a) in enumerate(list(zip(C, A))):
    b = max(0, i - N)
    w = min(i, N)
    while w >= max(0, i - N):
        #: :type: BinaryIndexedTree
        bit = bits[b][w]
        if b < N:
            inv = i - bit.sum(pos_b[b])
            dp[b + 1][w] = min(dp[b + 1][w], dp[b][w] + inv)

            if not bits[b + 1][w]:
                bits[b + 1][w] = bit.copy()
                bits[b + 1][w].add(pos_b[b], 1)
        if w < N:
            inv = i - bit.sum(pos_w[w])
            dp[b][w + 1] = min(dp[b][w + 1], dp[b][w] + inv)

            if not bits[b][w + 1]:
                bits[b][w + 1] = bit
                bits[b][w + 1].add(pos_w[w], 1)
        b += 1
        w -= 1
    # import numpy as np
    # print(np.array(dp))
    # print()
print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size

    def copy(self):
        ret = BinaryIndexedTree(0)
        ret._bit = self._bit[:]
        ret._size = self._size
        return ret


N = int(sys.stdin.buffer.readline())
CA = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(N * 2)]
C = []
A = []
for c, a in CA:
    a = int(a) - 1
    C.append(c)
    A.append(a)

pos_w = [-1] * N
pos_b = [-1] * N
ca = []
for i, (c, a) in enumerate(list(zip(C, A))):
    if c == 'W':
        pos_w[a] = i
    else:
        pos_b[a] = i

# dp[b][w]: 今までに B を b 個、W を w 個使ったときの答えの最小値
dp = [[INF] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
bits = [[None] * (N + 1) for _ in range(N + 1)]
bits[0][0] = BinaryIndexedTree(size=N * 2)
for i, (c, a) in enumerate(list(zip(C, A))):
    b = max(0, i - N)
    w = min(i, N)
    while w >= max(0, i - N):
        #: :type: BinaryIndexedTree
        bit = bits[b][w]
        if b < N:
            inv = i - bit.sum(pos_b[b])
            dp[b + 1][w] = min(dp[b + 1][w], dp[b][w] + inv)

            if not bits[b + 1][w]:
                bits[b + 1][w] = bit.copy()
                bits[b + 1][w].add(pos_b[b], 1)
        if w < N:
            inv = i - bit.sum(pos_w[w])
            dp[b][w + 1] = min(dp[b][w + 1], dp[b][w] + inv)

            if not bits[b][w + 1]:
                bits[b][w + 1] = bit.copy()
                bits[b][w + 1].add(pos_w[w], 1)
        b += 1
        w -= 1
    # import numpy as np
    # print(np.array(dp))
    # print()
print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:

"""

普通なら転倒数を計算すればよい
でも今回は…？

最終形を確定すればその転倒数を求めればよくなる
何処に白でどこに黒が良いのかを考える…？

2000 C 2 = 2*(10**6) 通り調べるか…？
1回で2000log2000かかるので無理

転倒数をdpする…？
黒の数を保持してdp → 4000 * 4000 log 4000

戻す場合も転倒数は同じ！！→最重要

まずlistに各色・番の初期位置を記録
BWを決めた時にその位置の数字は確定
その並び替えから元に戻す場合の転倒数を計算！！

"""

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

def cop(l):

    ret = []
    for i in l:
        ret.append(i)

    return ret


N = int(input())

Blis = [None] * (N+1)
Wlis = [None] * (N+1)

for i in range(N*2):

    c,a = input().split()
    a = int(a)

    if c == "B":
        Blis[a] = i+1
    else:
        Wlis[a] = i+1

#print (Blis)
#print (Wlis)

#各Bの数での最小の転倒数をBITと別リストで管理

BITs = [[0] * (2*N+1)]
revs = [float("inf")] * (N+1)
revs[0] = 0

#リストが大きすぎて毎回生成はあかん？→Bが大きい方から更新してけばおｋ
#必ず移行しなくてはいけない、具体的な転倒数のリストだけinfで初期化しておけばいい
#回が同じときのjでのBITの中味は固定→copyする必要なし…？

#BITにあらかじめBを置いておく
for i in range(N):

    new = cop(BITs[-1])
    bitadd (Blis[i+1] , 1 , new)
    BITs.append(new)


for i in range(2 * N):

    i += 1

    #BITの更新
    # ～i まで Wの処理をする

    for j in range(min(i , N + 1)):

        if i - j <= N:
            bitadd( Wlis[i-j] , 1 , BITs[j] )

    nrevs = [float("inf")] * (N+1)

    for j in range(min(i , N+1)):

        if i - j <= N:
            nrevs[j] = min(nrevs[j] , revs[j] + ( i - bitsum( Wlis[i-j] , BITs[j])))

        if j != N:
            nrevs[j+1] = min(nrevs[j+1] , revs[j] + (i - bitsum( Blis[j+1] , BITs[j+1] )))

    revs = nrevs
print (revs[-1])

Submission status: Time Limit Exceeded

Solution code:

"""

普通なら転倒数を計算すればよい
でも今回は…？

最終形を確定すればその転倒数を求めればよくなる
何処に白でどこに黒が良いのかを考える…？

2000 C 2 = 2*(10**6) 通り調べるか…？
1回で2000log2000かかるので無理

転倒数をdpする…？
黒の数を保持してdp → 4000 * 4000 log 4000

戻す場合も転倒数は同じ！！→最重要

まずlistに各色・番の初期位置を記録
BWを決めた時にその位置の数字は確定
その並び替えから元に戻す場合の転倒数を計算！！

"""

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


N = int(input())

Blis = [None] * (N+1)
Wlis = [None] * (N+1)

for i in range(N*2):

    c,a = input().split()
    a = int(a)

    if c == "B":
        Blis[a] = i+1
    else:
        Wlis[a] = i+1

#print (Blis)
#print (Wlis)

#各Bの数での最小の転倒数をBITと別リストで管理

BITs = [[0] * (2*N+1)]
revs = [float("inf")] * (N+1)
revs[0] = 0

#リストが大きすぎて毎回生成はあかん？→Bが大きい方から更新してけばおｋ
#必ず移行しなくてはいけない、具体的な転倒数のリストだけinfで初期化しておけばいい
#回が同じときのjでのBITの中味は固定→copyする必要なし…？

#BITにあらかじめBを置いておく
for i in range(N):

    new = BITs[-1].copy()
    bitadd (Blis[i+1] , 1 , new)
    BITs.append(new)


for i in range(2 * N):

    i += 1

    #BITの更新
    # ～i まで Wの処理をする

    for j in range(min(i , N + 1)):

        if i - j <= N:
            bitadd( Wlis[i-j] , 1 , BITs[j] )

    nrevs = [float("inf")] * (N+1)

    for j in range(min(i , N+1)):

        if i - j <= N:
            nrevs[j] = min(nrevs[j] , revs[j] + ( i - bitsum( Wlis[i-j] , BITs[j])))

        if j != N:
            nrevs[j+1] = min(nrevs[j+1] , revs[j] + (i - bitsum( Blis[j+1] , BITs[j+1] )))

    revs = nrevs
print (revs[-1])

Submission status: Time Limit Exceeded

Solution code:

"""

普通なら転倒数を計算すればよい
でも今回は…？

最終形を確定すればその転倒数を求めればよくなる
何処に白でどこに黒が良いのかを考える…？

2000 C 2 = 2*(10**6) 通り調べるか…？
1回で2000log2000かかるので無理

転倒数をdpする…？
黒の数を保持してdp → 4000 * 4000 log 4000

戻す場合も転倒数は同じ！！→最重要

まずlistに各色・番の初期位置を記録
BWを決めた時にその位置の数字は確定
その並び替えから元に戻す場合の転倒数を計算！！

"""

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


N = int(input())

Blis = [None] * (N+1)
Wlis = [None] * (N+1)

for i in range(N*2):

    c,a = input().split()
    a = int(a)

    if c == "B":
        Blis[a] = i+1
    else:
        Wlis[a] = i+1

#print (Blis)
#print (Wlis)

#各Bの数での最小の転倒数をBITと別リストで管理

BITs = [[0] * (2*N+1) for i in range(N+1) ]
revs = [float("inf")] * (N+1)
revs[0] = 0

#リストが大きすぎて毎回生成はあかん？→Bが大きい方から更新してけばおｋ
#必ず移行しなくてはいけない、具体的な転倒数のリストだけinfで初期化しておけばいい

for i in range(2 * N):
    i += 1

    newrevs = [float("inf")] * (N+1)

    for j in range(N,-1,-1):

        if revs[j] == float("inf"):
            continue

        if j < N:

            bitadd( Blis[j+1] , 1, BITs[j] )
            tempnrev = revs[j] + (i - bitsum(Blis[j+1] , BITs[j]))

            if tempnrev < newrevs[j+1]:
                newrevs[j+1] = tempnrev
                BITs[j+1] = BITs[j].copy()

            bitadd( Blis[j+1] , -1 , BITs[j])
            

        if i-j <= N:

            bitadd(Wlis[i - j] , 1 , BITs[j])
            newrevs[j] = revs[j] + (i - bitsum(Wlis[i-j] , BITs[j]))

    revs = newrevs

print (revs[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def main():
    inf = 5000
    n = int(input()[:-1])
    # iより前に色cのj以上が何個あるかがcnts[c][i][j]
    cnts = [[[0] * (n + 1) for _ in range(2 * n + 1)] for __ in range(2)]
    pos = [[0] * n for _ in range(2)]
    for i in range(n * 2):
        c, a = input().split()
        c = (c == "W") * 1
        a = int(a) - 1
        pos[c][a] = i
        for cc in range(2):
            for j in range(n):
                if c == cc and a >= j:
                    cnts[cc][i + 1][j] = cnts[cc][i][j] + 1
                else:
                    cnts[cc][i + 1][j] = cnts[cc][i][j]
    #    for x in cnts:
    #        print(x)
    #    print(pos)

    dp = [[inf] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for w in range(1, n + 1):
        i = pos[1][w - 1]
        dp[0][w] = dp[0][w - 1] + cnts[0][i][0] + cnts[1][i][w - 1]
    for b in range(1, n + 1):
        i = pos[0][b - 1]
        dp[b][0] = dp[b - 1][0] + cnts[0][i][b - 1] + cnts[1][i][0]
    for b in range(1, n + 1):
        for w in range(1, n + 1):
            bi = pos[0][b - 1]
            wi = pos[1][w - 1]
            dp[b][w] = min(dp[b - 1][w] + cnts[0][bi][b - 1] + cnts[1][bi][w],
                           dp[b][w - 1] + cnts[0][wi][b] + cnts[1][wi][w - 1])
    print(dp[n][n])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

before = {}
n = ni()
INF = 10**18

initial = []
for _ in range(2*n):
    ci, ai = ls()
    ai = int(ai)
    initial.append(ai if ci == "B" else n+ai)
    
lefts = set()
for ii in initial:
    before.update({ii: lefts.copy()})
    lefts.add(ii)
    
dp = [[INF]*(n+1) for _ in range(n+1)]
dp[0][0] = 0

blsets = [[set()]*(n+1) for _ in range(n+1)]

blacks = [set() for _ in range(n+1)]
whites = [set() for _ in range(n+1)]

black = set()
white = set()

for i in range(1,n+1):
    black.add(i)
    white.add(n+i)
    blacks[i] = black.copy()
    whites[i] = white.copy()

for i in range(n+1):
    for j in range(n+1):
        blsets[i][j] = blacks[i] | whites[j]



for j in range(1,n+1):
    dp[0][j] = dp[0][j-1] + len(before[n+j]) - len(before[n+j] & blsets[0][j-1])

for i in range(1,n+1):
    dp[i][0] = dp[i-1][0] + len(before[i]) - len(before[i] & blsets[i-1][0])

for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = min(dp[i-1][j] + len(before[i]) - len(before[i] & blsets[i-1][j]),
                       dp[i][j-1] + len(before[n+j]) - len(before[n+j] & blsets[i][j-1]))
        
print(dp[n][n])

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

before = {}
n = ni()
INF = 10**18

initial = []
for _ in range(2*n):
    ci, ai = ls()
    ai = int(ai)
    initial.append(ai if ci == "B" else n+ai)
    
lefts = set()
for ii in initial:
    before.update({ii: lefts.copy()})
    lefts.add(ii)
    
dp = [[INF]*(n+1) for _ in range(n+1)]
dp[0][0] = 0

for j in range(1,n+1):
    dp[0][j] = dp[0][j-1] + len(before[n+j] - set([k for k in range(n+1,n+j)]))

for i in range(1,n+1):
    dp[i][0] = dp[i-1][0] + len(before[i] - set([k for k in range(1,i)]))

for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = min(dp[i-1][j] + len(before[i] - set([k for k in range(1,i)] + [k for k in range(n+1,n+j+1)])),
                       dp[i][j-1] + len(before[n+j] - set([k for k in range(1,i+1)] + [k for k in range(n+1,n+j)])))
        
print(dp[n][n])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import heapq


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * n

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

    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i |= i + 1

INF = 10 ** 9

bit_w = None
bit_b = None


def solve(n, w, b):

    length_h = [[0] * (n + 1) for _ in range(n + 1)]
    length_v = [[0] * (n + 1) for _ in range(n + 1)]

    for y in range(n):
        for x in range(n):
            length_h[x][y] = bit_b.sum(w[x])
        bit_b.add(b[y], -1)
    for x in range(n):
        length_h[x][n] = bit_b.sum(w[x])

    for x in range(n):
        for y in range(n):
            length_v[x][y] = bit_w.sum(b[y])
        bit_w.add(w[x], -1)
    for y in range(n):
        length_v[n][y] = bit_w.sum(b[y])


    dist = [[INF] * (n + 1) for _ in range(n + 1)]
    dist[0][0] = 0
    pq = []
    heapq.heappush(pq, (0, 0, 0))

    while pq:
        d, x, y = heapq.heappop(pq)
        if x < n:
            alt = dist[x][y] + length_h[x][y]
            if alt < dist[x + 1][y]:
                dist[x + 1][y] = alt
                heapq.heappush(pq, (alt, x + 1, y))
        if y < n:
            alt = dist[x][y] + length_v[x][y]
            if alt < dist[x][y + 1]:
                dist[x][y + 1] = alt
                heapq.heappush(pq, (alt, x, y + 1))

    ans = dist[n][n]
    for i in range(n):
        for j in range(i + 1, n):
            if w[j] < w[i]:
                ans += 1
            if b[j] < b[i]:
                ans += 1

    return ans


def main():
    global bit_w, bit_b

    n = input()
    n = int(n)
    w = [0] * n
    b = [0] * n
    bit_w = Bit(2 * n)
    bit_b = Bit(2 * n)
    for i in range(2 * n):
        c, a = input().split()
        a = int(a) - 1
        if c == 'W':
            w[a] = i
            bit_w.add(i, 1)
        else:
            b[a] = i
            bit_b.add(i, 1)


    print(solve(n, w, b))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
data = []
for i in range(N*2):
    c,a = input().split()
    aa = int(a)
    data.append([c,aa-1])

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

white = []
wb = []
for i in range(N):
    counter = 0
    for c,a in data:
        if c == 'W' and a == i:
            white.append(counter)
            break
        elif c == 'W' and a > i:
            counter += 1
    jset = []
    for j in range(N+1):
        counter = 0
        for c,a in data:
            if c == 'W' and a == i:
                jset.append(counter)
                break
            elif c == 'B' and a >=j:
                counter += 1
    wb.append(jset)

black = []
bw = []
for i in range(N):
    counter = 0
    for c,a in data:
        if c == 'B' and a == i:
            black.append(counter)
            break
        elif c == 'B' and a > i:
            counter += 1
        
    jset = []    
    for j in range(N+1):
        counter = 0
        for c,a in data:
            if c == 'B' and a == i:
                jset.append(counter)
                break
            elif c == 'W' and a >=j:
                counter += 1
    bw.append(jset)

# dp[0][0] = 0
for b in range(N+1):
    for w in range(N+1):
        if b==0 and w == 0:
            pass
        elif b == 0:
            dp[b][w] = dp[b][w-1]+white[w-1]+wb[w-1][b]
        elif w == 0:
            dp[b][w] = dp[b-1][w]+black[b-1]+bw[b-1][w]
        else:
            dp[b][w] = min(dp[b][w-1]+white[w-1]+wb[w-1][b],dp[b-1][w]+black[b-1]+bw[b-1][w])   
print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
inf,dp2 = float("inf"),[[[0]*(n+1) for i in range(2*n+1)] for i in range(2)]
dp,y,bw = [[inf]*(n+1) for i in range(n+1)],[-1,-1],[[] for i in range(2)]
dp[0][0] = 0
for j in range(2*n):
	c,a = (i for i in input().split())
	if c=="B": c = 0
	else: c = 1
	a = int(a)
	for i in range(n+1):
		for k in range(y[c]+1,j+1): dp2[c][k][i] = dp2[c][k-1][i]
	for i in range(a+1): dp2[c][j+1][i] = dp2[c][j][i]+1
	for i in range(a+1,n+1): dp2[c][j+1][i] = dp2[c][j][i]
	y[c] = j+1
	bw[c].append([a,j])
for i in range(2): bw[i].sort()
for i in range(n+1):
		for k in range(y[1-c]+1,2*n+1): dp2[1-c][k][i] = dp2[1-c][k-1][i]
for i in range(1,n+1): dp[i][0] = dp[i-1][0]+dp2[0][bw[0][i-1][1]][i]+dp2[1][bw[0][i-1][1]+1][1]
for j in range(1,n+1): dp[0][j] = dp[0][j-1]+dp2[1][bw[1][j-1][1]][j]+dp2[0][bw[1][j-1][1]+1][1]
for i in range(1,n):
	for j in range(1,n): dp[i][j] = min(dp[i-1][j]+dp2[0][bw[0][i-1][1]][i]+dp2[1][bw[0][i-1][1]+1][j+1],dp[i][j-1]+dp2[1][bw[1][j-1][1]][j]+dp2[0][bw[1][j-1][1]+1][i+1])
for i in range(1,n): dp[i][n] = min(dp[i-1][n]+dp2[0][bw[0][i-1][1]][i],dp[i][n-1]+dp2[1][bw[1][n-1][1]][n]+dp2[0][bw[1][n-1][1]+1][i+1])
for j in range(1,n): dp[n][j] = min(dp[n-1][j]+dp2[0][bw[0][n-1][1]][n]+dp2[1][bw[0][n-1][1]+1][j+1],dp[n][j-1]+dp2[1][bw[1][j-1][1]][j])
print(min(dp[n][n-1],dp[n-1][n]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = []
C = []
A = []
b = w = 0
b_d = {}
w_d = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    n = 0
    for cc, aa in zip(C, A):
        if cc == c and aa > a:
            n += 1
    L.append([0] * (N + 1))
    cnt = 0
    for j in range(N, -1, -1):
        L[-1][j] = cnt+n
        if j in (b_d if c=="W" else w_d):
            cnt+=1

    if c=="B":
        b_d[a] = i
        b+=1
    else:
        w_d[a] = i
        w+=1
    C.append(c)
    A.append(a)
#print(L, b_d, w_d)

dp = [[0]*(N+2) for i in range(N+2)]
for i in range(N+1):
    for j in range(N+1):
        if i==j==0:
            continue
        if i==0:
            dp[i][j] = dp[i][j-1] + L[b_d[j]][i]
        elif j==0:
            dp[i][j] = dp[i-1][j] + L[w_d[i]][j]
        else:
            dp[i][j] = min(dp[i-1][j] + L[w_d[i]][j],
                           dp[i][j-1] + L[b_d[j]][i])
print(dp[-2][-2])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n = f.read_int()
    b = [None] * (2*n)
    d = {}
    for i in xrange(2*n):
        ci, ai = f.read_str_list()
        b[i] = (ci, int(ai))
        d[(ci, int(ai))] = i+1

    bit = BinaryIndexedTree(2*n)
    for i in xrange(1,2*n+1):
        bit.add(i,1)

    dp = [[float('inf')]*(n+1) for _ in xrange(n+1)]
    dp[0][0] = 0

    for wi in xrange(n+1):
        for bi in xrange(n+1):
            if bi < n: dp[wi][bi+1] = min(dp[wi][bi+1], dp[wi][bi] + bit.sum(d[('B', bi+1)]-1))
            if wi < n: dp[wi+1][bi] = min(dp[wi+1][bi], dp[wi][bi] + bit.sum(d[('W', wi+1)]-1))
            if bi < n: bit.add(d[('B', bi+1)], -1)
        for bi in xrange(n):
            bit.add(d[('B', bi+1)], 1)
        if wi < n: bit.add(d[('W', wi+1)], -1)

    return dp[n][n]


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in range(size + 1)]
        self.size = size

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

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


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [0] + list(accumulate(c[y] for y, c in zip(rev[1], cost[1])))
    for x, cw0, cw1 in zip(rev[0], cost[0], cost[0][1:]):
        ndp = [0] * (n + 1)
        cw0x = cw0[x]
        ndp[0] = prev = dp[0] + cw0x
        for b, (y, cb0, cb1) in enumerate(zip(rev[1], cost[1], cost[1][1:])):
            ndp[b + 1] = prev = min(dp[b + 1] + cw0x + cb1[x], prev + cw1[y] + cb0[y])
        dp = ndp
    return dp[n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))