본문 바로가기

카테고리 없음

[백준 9463번] 순열 그래프 (Python3)

def update(i):
  while i<M:
    fen[i] += 1
    i += i&-i

def SUM(i):
  S = 0
  while i:
    S += fen[i]
    i -= i&-i
  return S

for _ in range(int(input())):
  N = int(input()); M = 1<<17
  
  D1,D2 = [[*map(int,input().split())] for i in range(2)]
  Index = [0]*(N+1)
  for i in range(N):
    Index[D1[i]] = i+1
  
  fen = [0]*M
  result = 0
  
  for i in range(1,N+1):
    idx = Index[D2[-i]]
    result += SUM(idx)
    update(idx)
  print(result)

= 공장 [백준 7578번] 공장 (Python3) (tistory.com)

 

다만 시간제한이 다소 빡빡하여 파이썬의 경우 억까당할 수 있기 때문에 pypy3로 제출하는걸 추천한다.

내 코드가 python3로 제출한 코드 중 유일하게 통과되었다.