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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return map(int, input().split())

N = int(input())
balls = [input().replace(" ", "") for _ in range(2*N)]
#balls2 = balls + ["END"]
#balls = balls + ["END"]

def get_l(X, balls):
    if len(X):
        return balls.index(X[0])
    else:
        return 4000

def get_r(X, balls):
    if len(X):
        return balls.index(X[-1])
    else:
        return -4000

B = deque(["B{}".format(i) for i in range(1, N+1)])
W = deque(["W{}".format(i) for i in range(1, N+1)])

l = 0
r = 2*N-1
ans = 0

while l < r:
    bl = get_l(B, balls)
    wl = get_l(W, balls)
    br = get_r(B, balls)
    wr = get_r(W, balls)
    m = min(bl - l, wl - l, r - wr, r - br)
    
    if bl - l ==  m:
        if bl != l:
            ans += bl-l
            del balls[bl]
            balls.insert(l, B[0])
        B.popleft()
        l += 1
    elif wl - l ==  m:
        if wl != l:
            ans += wl-l
            del balls[wl]
            balls.insert(l, W[0])
        W.popleft()
        l += 1
    
    elif r - br ==  m:
        if br != r:
            ans += r - br
            balls.insert(r, B[-1])
            del balls[br]
        B.pop()
        r -= 1

    elif r - wr ==  m:
        if wr != r:
            ans += r - wr
            balls.insert(r, W[-1])
            del balls[wr]
        W.pop()
        r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l=[]
for i in range(2*N):
    l.append(input().split())

ans=0
#print(ans,l)
b=1
w=1
M=2*N+1
for i in range(2*N-1):
    bf=M
    wf=M
    if ["B",str(b)] in l:
        bf=l.index(["B",str(b)])
    if ["W",str(w)] in l:
        wf=l.index(['W',str(w)])
    
    if bf<wf:
        ans+=bf
        del(l[bf])
        b+=1
    else:
        ans+=wf
        del(l[wf])
        w+=1
#    print(ans,l)    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
N = int(input())
balls = [input().replace(" ", "") for _ in range(2*N)] + ["END"]

B = ["END"] + ["B{}".format(i) for i in range(1, N+1)[::-1]]
W = ["END"] + ["W{}".format(i) for i in range(1, N+1)[::-1]]

ans = 0
for i in range(2*N):
    b = balls.index(B[-1])
    w = balls.index(W[-1])
    if b < w:
        if b != i:
            ans += b-i
            del balls[b]
            balls.insert(i, B[-1])
        B.pop()
    else:
        if w != i:
            ans += w-i
            del balls[w]
            balls.insert(i, W[-1])
        W.pop()

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
N = int(input())
balls = [input().replace(" ", "") for _ in range(2*N)] + ["END"]

B = ["END"] + ["B{}".format(i) for i in range(1, N+1)[::-1]]
W = ["END"] + ["W{}".format(i) for i in range(1, N+1)[::-1]]

ans = 0
for i in range(2*N - 1):
    b = balls.index(B[-1])
    w = balls.index(W[-1])
    if b < w:
        if b != i:
            ans += b-i
            del balls[b]
            balls.insert(i, B[-1])
        B.pop()
    else:
        if w != i:
            ans += w-i
            del balls[w]
            balls.insert(i, W[-1])
        W.pop()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
import sys
input = sys.stdin.readline
from copy import deepcopy
n = int(input())
ca = [input().rstrip() for i in range(2*n)]
dc = [0]*(2*n+1)
for i in range(2*n):
  if ca[i][0] == "W":
    dc[int(ca[i][2])] = i+1
  else:
    dc[n+int(ca[i][2])] = i+1
dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
bit0 = Bit(2*n)
for i in range(n+1):
  wx = dc[i+1]
  if i:
    bit0.add(dc[i],1)
  if i < n:
    dp[i+1][0] = dp[i][0]+wx-bit0.sum(wx)-1
  bitc = deepcopy(bit0)
  for j in range(n+1):
    if i < n:
      dp[i+1][j] = dp[i][j]+wx-bitc.sum(wx)-1
    if j < n:
      bx = dc[n+j+1]
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+bx-bitc.sum(bx)-1)
      bitc.add(bx,1)
      #print(i,j,dc[bx],bitc.sum(dc[bx]))
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
import sys
input = sys.stdin.readline
from copy import deepcopy
def main():
  n = int(input())
  ca = [input().rstrip() for i in range(2*n)]
  dc = {ca[i]:i+1 for i in range(2*n)}
  dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
  dp[0][0] = 0
  bit0 = Bit(2*n)
  for i in range(n+1):
    wx = "W "+str(i+1)
    wp = "W "+str(i)
    if i:
      bit0.add(dc[wp],1)
    if i < n:
      dp[i+1][0] = dp[i][0]+dc[wx]-bit0.sum(dc[wx])-1
    bitc = deepcopy(bit0)
    for j in range(n+1):
      bx = "B "+str(j+1)
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+dc[bx]-bitc.sum(dc[bx])-1)
      if i < n:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+dc[wx]-bitc.sum(dc[wx])-1)
      if j < n:
        bitc.add(dc[bx],1)
        #print(i,j,dc[bx],bitc.sum(dc[bx]))
  print(dp[-1][-1])
main()

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
import sys
input = sys.stdin.readline
from copy import deepcopy
def main():
  n = int(input())
  ca = [input().rstrip() for i in range(2*n)]
  dc = {ca[i]:i+1 for i in range(2*n)}
  dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
  dp[0][0] = 0
  bit0 = Bit(2*n)
  for i in range(n+1):
    wx = "W "+str(i+1)
    wp = "W "+str(i)
    if i:
      bit0.add(dc[wp],1)
    if i < n:
      dp[i+1][0] = dp[i][0]+dc[wx]-bit0.sum(dc[wx])-1
    bitc = deepcopy(bit0)
    for j in range(n+1):
      bx = "B "+str(j+1)
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+dc[bx]-bitc.sum(dc[bx])-1)
      if i < n:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+dc[wx]-bitc.sum(dc[wx])-1)
      if j < n:
        bitc.add(dc[bx],1)
        #print(i,j,dc[bx],bitc.sum(dc[bx]))
  print(dp[-1][-1])
main()

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
import sys
input = sys.stdin.readline
from copy import deepcopy
n = int(input())
ca = [input().rstrip() for i in range(2*n)]
dc = [0]*(2*n+1)
for i in range(2*n):
  if ca[i][0] == "W":
    dc[int(ca[i][2])] = i+1
  else:
    dc[n+int(ca[i][2])] = i+1
dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
bit0 = Bit(2*n)
for i in range(n+1):
  wx = dc[i+1]
  if i:
    bit0.add(dc[i],1)
  if i < n:
    dp[i+1][0] = dp[i][0]+wx-bit0.sum(wx)-1
  bitc = deepcopy(bit0)
  for j in range(n+1):
    if i < n:
      dp[i+1][j] = dp[i][j]+wx-bitc.sum(wx)-1
    if j < n:
      bx = dc[n+j+1]
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+bx-bitc.sum(bx)-1)
      bitc.add(bx,1)
      #print(i,j,dc[bx],bitc.sum(dc[bx]))
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
import sys
input = sys.stdin.readline
from copy import deepcopy
n = int(input())
ca = [input().rstrip() for i in range(2*n)]
dc = [0]*(2*n+1)
for i in range(2*n):
  if ca[i][0] == "W":
    dc[int(ca[i][2])] = i+1
  else:
    dc[n+int(ca[i][2])] = i+1
dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
bit0 = Bit(2*n)
for i in range(n+1):
  wx = i+1
  wp = i
  if i:
    bit0.add(dc[wp],1)
  if i < n:
    dp[i+1][0] = dp[i][0]+dc[wx]-bit0.sum(dc[wx])-1
  bitc = deepcopy(bit0)
  for j in range(n+1):
    bx = n+j+1
    if j < n:
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+dc[bx]-bitc.sum(dc[bx])-1)
    if i < n:
      dp[i+1][j] = min(dp[i+1][j],dp[i][j]+dc[wx]-bitc.sum(dc[wx])-1)
    if j < n:
      bitc.add(dc[bx],1)
      #print(i,j,dc[bx],bitc.sum(dc[bx]))
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
import sys
input = sys.stdin.readline
from copy import deepcopy
from collections import defaultdict
n = int(input())
ca = [input().rstrip() for i in range(2*n)]
dcw = defaultdict(int)
dcb = defaultdict(int)
for i in range(2*n):
  if ca[i][0] == "W":
    dcw[int(ca[i][2])] = i+1
  else:
    dcb[int(ca[i][2])] = i+1
dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
bit0 = Bit(2*n)
for i in range(n+1):
  if i:
    bit0.add(dcw[i],1)
  if i < n:
    dp[i+1][0] = dp[i][0]+dcw[i+1]-bit0.sum(dcw[i+1])-1
  bitc = deepcopy(bit0)
  for j in range(n+1):
    if j < n:
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+dcb[j+1]-bitc.sum(dcb[j+1])-1)
    if i < n:
      dp[i+1][j] = dp[i][j]+dcw[i+1]-bitc.sum(dcw[i+1])-1
    if j < n:
      bitc.add(dcb[j+1],1)
      #print(i,j,dc[bx],bitc.sum(dc[bx]))
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
import sys
input = sys.stdin.readline
from copy import deepcopy
n = int(input())
ca = [input().rstrip() for i in range(2*n)]
dc = {ca[i]:i+1 for i in range(2*n)}
dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
bit0 = Bit(2*n)
for i in range(n+1):
  wx = "W "+str(i+1)
  wp = "W "+str(i)
  if i:
    bit0.add(dc[wp],1)
  if i < n:
    dp[i+1][0] = dp[i][0]+dc[wx]-bit0.sum(dc[wx])-1
  bitc = deepcopy(bit0)
  for j in range(n+1):
    bx = "B "+str(j+1)
    if j < n:
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+dc[bx]-bitc.sum(dc[bx])-1)
    if i < n:
      dp[i+1][j] = min(dp[i+1][j],dp[i][j]+dc[wx]-bitc.sum(dc[wx])-1)
    if j < n:
      bitc.add(dc[bx],1)
      #print(i,j,dc[bx],bitc.sum(dc[bx]))
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]
    dct = {(a, b): i for i, (a, b) in enumerate(ab)}

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a == "B":
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    for i in range(n+1):
        dp1 = dp[i]
        if i < n:
            dp2 = dp[i+1]
            t = dct[("B", i)]
        for j in range(n+1):
            d = dp1[j]
            if i < n:
                dp2[j] = min(dp2[j], d+lb[t][i]+lw[t][j])
            if j < n:
                t2 = dct[("W", j)]
                dp1[j+1] = min(dp1[j+1], d+lb[t2][i]+lw[t2][j])
    print(dp[n][n])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]
    dct = {(a, b): i for i, (a, b) in enumerate(ab)}

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a == "B":
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    for i in range(n+1):
        try:
            t = dct[("B", i)]
        except:
            pass
        for j in range(n+1):
            d = dp[i][j]
            try:
                dp[i+1][j] = min(dp[i+1][j], d+lb[t][i]+lw[t][j])
            except:
                pass
            try:
                t2 = dct[("W", j)]
                dp[i][j+1] = min(dp[i][j+1], d+lb[t2][i]+lw[t2][j])
            except:
                pass
    print(dp[n][n])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    # 一点更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i):
            x, n, bit = i+1, self.n, self.bit
            while x < n+1:
                bit[x] += 1
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]

    f_B = [[0]*n for _ in [0]*(n+1)]  # f_B[i][j] = Bがi個、Wがj個あるときのBを置く手数
    f_W = [[0]*n for _ in [0]*(n+1)]  # f_W[i][j] = Bがi個、Wがj個あるときのWを置く手数
    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # まずf_Bから出す
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        f = f_B[i]
        for a, b in ab:
            if a == "B":
                f[b] = bit.sum(n-b-1)+cnt
                bit.add(n-b-1)
            else:
                if b >= i:
                    cnt += 1
    # f_Wも同様
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        f = f_W[i]
        for a, b in ab:
            if a == "W":
                f_W[i][b] = bit.sum(n-b-1)+cnt
                bit.add(n-b-1)
            else:
                if b >= i:
                    cnt += 1
    for i in range(n+1):
        for j in range(n+1):
            d = dp[i][j]
            try:
                dp[i+1][j] = min(dp[i+1][j], d+f_B[j][i])
            except:
                pass
            try:
                dp[i][j+1] = min(dp[i][j+1], d+f_W[i][j])
            except:
                pass
    print(dp[n][n])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    # 一点更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i):
            x, n, bit = i+1, self.n, self.bit
            while x < n+1:
                bit[x] += 1
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]

    f_B = [[0]*(n+1) for _ in [0]*n]  # f_B[i][j] = Bがi個、Wがj個あるときのBを置く手数
    f_W = [[0]*(n+1) for _ in [0]*n]  # f_W[i][j] = Bがi個、Wがj個あるときのWを置く手数
    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # まずf_Bから出す
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "B":
                f_B[b][i] = bit.sum(n-b-1)+cnt
                bit.add(n-b-1)
            else:
                if b >= i:
                    cnt += 1
    # f_Wも同様
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "W":
                f_W[b][i] = bit.sum(n-b-1)+cnt
                bit.add(n-b-1)
            else:
                if b >= i:
                    cnt += 1
    for i in range(n+1):
        for j in range(n+1):
            d = dp[i][j]
            try:
                dp[i+1][j] = min(dp[i+1][j], d+f_B[i][j])
            except:
                pass
            try:
                dp[i][j+1] = min(dp[i][j+1], d+f_W[j][i])
            except:
                pass
    print(dp[n][n])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    # 一点更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(n))-3)
            self.bit = [0]*(n+1)
            self.allsum = 0

        # 初期化する
        def make_bit(self, a):
            n, bit = self.n, self.bit
            for i, j in enumerate(a):
                x = i+1
                self.allsum += j
                while x < n+1:
                    bit[x] += j
                    x += x & (-x)

        # 位置iに値vを足す
        def add(self, i, v):
            x, n, bit = i+1, self.n, self.bit
            self.allsum += v
            while x < n+1:
                bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

        # 和がw以上となる最小のインデックスを求める
        def lowerbound(self, w):
            if w <= 0:
                return 0
            x, k, n, bit = 0, self.maxbit, self.n, self.bit
            while k:
                if x+k <= n and bit[x+k] < w:
                    w -= bit[x+k]
                    x += k
                k //= 2
            return x

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]

    f_B = [[0]*(n+1) for _ in [0]*n]  # f_B[i][j] = Bがi個、Wがj個あるときのBを置く手数
    f_W = [[0]*(n+1) for _ in [0]*n]  # f_W[i][j] = Bがi個、Wがj個あるときのWを置く手数
    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # まずf_Bから出す
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "B":
                f_B[b][i] = bit.allsum-bit.sum(b)+cnt
                bit.add(b, 1)
            else:
                if b >= i:
                    cnt += 1
    # f_Wも同様
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "W":
                f_W[b][i] = bit.allsum-bit.sum(b)+cnt
                bit.add(b, 1)
            else:
                if b >= i:
                    cnt += 1
    for i in range(n+1):
        for j in range(n+1):
            d = dp[i][j]
            try:
                dp[i+1][j] = min(dp[i+1][j], d+f_B[i][j])
            except:
                pass
            try:
                dp[i][j+1] = min(dp[i][j+1], d+f_W[j][i])
            except:
                pass
    print(dp[n][n])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    # 一点更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(n))-3)
            self.bit = [0]*(n+1)
            self.allsum = 0

        # 初期化する
        def make_bit(self, a):
            n, bit = self.n, self.bit
            for i, j in enumerate(a):
                x = i+1
                self.allsum += j
                while x < n+1:
                    bit[x] += j
                    x += x & (-x)

        # 位置iに値vを足す
        def add(self, i, v):
            x, n, bit = i+1, self.n, self.bit
            self.allsum += v
            while x < n+1:
                bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

        # 和がw以上となる最小のインデックスを求める
        def lowerbound(self, w):
            if w <= 0:
                return 0
            x, k, n, bit = 0, self.maxbit, self.n, self.bit
            while k:
                if x+k <= n and bit[x+k] < w:
                    w -= bit[x+k]
                    x += k
                k //= 2
            return x

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]

    f_B = [[10**9]*(n+1) for _ in [0]*n]  # f_B[i][j] = Bがi個、Wがj個あるときのBを置く手数
    f_W = [[10**9]*(n+1) for _ in [0]*n]  # f_W[i][j] = Bがi個、Wがj個あるときのWを置く手数
    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # まずf_Bから出す
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "B":
                f_B[b][i] = bit.allsum-bit.sum(b)+cnt
                bit.add(b, 1)
            else:
                if b >= i:
                    cnt += 1
    # f_Wも同様
    for i in range(n+1):
        bit = BIT(n)
        cnt = 0
        for a, b in ab:
            if a == "W":
                f_W[b][i] = bit.allsum-bit.sum(b)+cnt
                bit.add(b, 1)
            else:
                if b >= i:
                    cnt += 1
    for i in range(n+1):
        for j in range(n+1):
            d = dp[i][j]
            try:
                dp[i+1][j] = min(dp[i+1][j], d+f_B[i][j])
            except:
                pass
            try:
                dp[i][j+1] = min(dp[i][j+1], d+f_W[j][i])
            except:
                pass
    print(dp[n][n])


main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[0]*2*n
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  bitt=bit[:]
  for j in range(n):
    a=0
    k=2*n
    while k:
      a+=bitt[k-1]
      k-=k&-k
    if w[j]!=0:
      k=w[j]
      while k:
        a-=bitt[k-1]
        k-=k&-k
    dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a+w[j]-(i+j))
    k=w[j]+1
    while k<=2*n:
      bitt[k-1]+=1
      k+=k&-k
    if i!=n:
      a=0
      k=2*n
      while k:
        a+=bitt[k-1]
        k-=k&-k
      if b[i]!=0:
        k=b[i]
        while k:
          a-=bitt[k-1]
          k-=k&-k
      dp[i+1][j+1]=dp[i][j+1]+a+b[i]-(i+j+1)
  if i!=n:
    a=b[i]-i
    k=2*n
    while k:
      a+=bit[k-1]
      k-=k&-k
    if b[i]!=0:
      k=b[i]
      while k:
        a-=bit[k-1]
        k-=k&-k
    dp[i+1][0]=dp[i][0]+a
    k=b[i]+1
    while k<=2*n:
      bit[k-1]+=1
      k+=k&-k
print(dp[n][n])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
  n=int(input())
  b=[0]*n
  w=[0]*n
  for i in range(2*n):
    c,a=input().split()
    if c=="B":b[int(a)-1]=i
    else:w[int(a)-1]=i
  bit=[2*n*[0]for _ in range(n+1)]
  dp=[(n+1)*[10**10]for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n+1):
    dp[i][0]=0
    for k in range(i):
      a=0
      ind=2*n
      while ind:
        a+=bit[i][ind-1]
        ind-=ind&-ind
      if w[k]!=0:
        ind=w[k]
        while ind:
          a-=bit[i][ind-1]
          ind-=ind&-ind
      dp[i][0]+=w[k]+a-k
      ind=w[k]+1
      while ind<=2*n:
        bit[i][ind-1]+=1
        ind+=ind&-ind
  for j in range(n):
    for i in range(n+1):
      ba=0
      ind=2*n
      while ind:
        ba+=bit[i][ind-1]
        ind-=ind&-ind
      if b[j]!=0:
        ind=b[j]
        while ind:
          ba-=bit[i][ind-1]
          ind-=ind&-ind
      if i==0:
        dp[i][j+1]=dp[i][j]+b[j]+ba-(i+j)
      else:
        dp[i][j+1]=dp[i][j]+(b[j]+ba-(i+j))
        wa=0
        ind=2*n
        while ind:
          wa+=bit[i-1][ind-1]
          ind-=ind&-ind
        if w[i-1]!=0:
          ind=w[i-1]
          while ind:
            wa-=bit[i-1][ind-1]
            ind-=ind&-ind
        dp[i][j+1]=min(dp[i][j+1],dp[i-1][j+1]+(w[i-1]+wa-(i+j)))
      ind=b[j]+1
      while ind<=2*n:
        bit[i][ind-1]+=1
        ind+=ind&-ind
  print(dp[n][n])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[2*n*[0]for _ in range(n+1)]
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  dp[i][0]=0
  for k in range(i):
    a=0
    ind=2*n
    while ind:
      a+=bit[i][ind-1]
      ind-=ind&-ind
    if w[k]!=0:
      ind=w[k]
      while ind:
        a-=bit[i][ind-1]
        ind-=ind&-ind
    dp[i][0]+=w[k]+a-k
    ind=w[k]+1
    while ind<=2*n:
      bit[i][ind-1]+=1
      ind+=ind&-ind
for j in range(n):
  for i in range(n+1):
    ba=0
    ind=2*n
    while ind:
      ba+=bit[i][ind-1]
      ind-=ind&-ind
    if b[j]!=0:
      ind=b[j]
      while ind:
        ba-=bit[i][ind-1]
        ind-=ind&-ind
    if i==0:
      dp[i][j+1]=dp[i][j]+b[j]+ba-(i+j)
    else:
      dp[i][j+1]=dp[i][j]+(b[j]+ba-(i+j))
      wa=0
      ind=2*n
      while ind:
        wa+=bit[i-1][ind-1]
        ind-=ind&-ind
      if w[i-1]!=0:
        ind=w[i-1]
        while ind:
          wa-=bit[i-1][ind-1]
          ind-=ind&-ind
      dp[i][j+1]=min(dp[i][j+1],dp[i-1][j+1]+(w[i-1]+wa-(i+j)))
    ind=b[j]+1
    while ind<=2*n:
      bit[i][ind-1]+=1
      ind+=ind&-ind
print(dp[n][n])

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[BinaryIndexedTree(2*n)for _ in range(n+1)]
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  dp[i][0]=0
  for k in range(i):
    dp[i][0]+=w[k]+bit[i].sum(w[k],2*n-1)-k
    bit[i].add(w[k],1)
for j in range(n):
  for i in range(n+1):
    if i==0:
      dp[i][j+1]=dp[i][j]+b[j]+bit[i].sum(b[j],2*n-1)-(i+j)
    else:
      dp[i][j+1]=dp[i][j]+(b[j]+bit[i].sum(b[j],2*n-1)-(i+j))
      dp[i][j+1]=min(dp[i][j+1],dp[i-1][j+1]+(w[i-1]+bit[i-1].sum(w[i-1],2*n-1)-(i+j)))
    bit[i].add(b[j],1)
print(dp[n][n])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
INF = 10 ** 9
info = [list(input().split()) for i in range(2 * n)]

ind = {}
for i in range(2 * n):
    info[i] = (info[i][0], int(info[i][1]))
    ind[info[i]] = i

ru_b = [[0] * (2 * n + 1) for i in range(n + 1)]
ru_w = [[0] * (2 * n + 1) for i in range(n + 1)]
for i in range(n + 1):
    for j in range(2 * n):
        col, num = info[j]
        if col == "B" and num > i:
            ru_b[i][j + 1] += 1
        if col == "W" and num > i:
            ru_w[i][j + 1] += 1
    for j in range(2 * n):
        ru_b[i][j + 1] += ru_b[i][j]
        ru_w[i][j + 1] += ru_w[i][j]    


dp = [[INF] * (n + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n + 1):
    for j in range(n + 1):
        if i + 1 <= n and j <= n:
            bi = ind[("B", i + 1)]
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + ru_b[i][bi] + ru_w[j][bi])
        if i <= n and j + 1 <= n:
            wi = ind[("W", j + 1)]
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + ru_w[j][wi] + ru_b[i][wi])

print(dp[-1][-1])