글 읽기 - 어떤 부분에서 시간초과가 나는지 모르겠습니다.

ine 2년 전 1

세그먼트 트리와 해쉬로 풀었습니다.

시간 복잡도는 O(t * n * logn)입니다.

마음에 걸리는 점은, 테스트 케이스가 t개라서 이거에 따라 시간 초과가 나는 것인지...

7578번 문제와 완전 똑같은데 차이점이 테스트 케이스가 t개가 있다 뿐이라서 이런 생각이 들었습니다.

고수님들 고견 부탁드리겠습니다!

from math import log2, ceil
import sys
input = sys.stdin.readline
def subsum(node, start, end, left, right):
    if right < start or end < left:
        return 0
    if left <= start and end <= right:
        return tree[node]
    return subsum(node*2, start, (start+end)//2, left, right) + \
           subsum(node*2+1, (start+end)//2 + 1, end, left, right)
def update(node, start, end, index):
    if not (start <= index <= end):
        return
    if start == end:
        tree[node] += 1
        return
    update(node*2, start, (start+end)//2, index)
    update(node*2+1, (start+end)//2+1, end, index)
    tree[node] = tree[node*2] + tree[node*2 + 1]
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    a_hash = {}
    b_hash = {}
    for i in range(n):
        a_hash[a[i]] = i
        b_hash[b[i]] = i
    h = int(ceil(log2(n)))
    tree = [0]*(2**(h+1))
    ans = 0
    for i in range(n):
        aval = a[i]
        idx = b_hash[aval]
        update(1,0,n-1,idx)
        ans += subsum(1,0,n-1,idx+1,n-1)
    print(ans)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 부분에서 시간초과가 나는지 모르겠습니다.

ine 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말