spark_1130   2년 전

해당 문제를 pypy3 기준으로 제출할 경우,

파이썬 내장 정렬 함수를 이용해서 너무 쉽게 풀이가 됩니다.

정렬 후에 딕셔너리를 이용해서 좌표 압축을 하고, 각 숫자가 원래 어떤 인덱스였는지를 표현해주면 풀이가 완성됩니다.

arr: 1 5 2 6 3 7 4

idx: 0 1 2 3 4 5 6

=>

arr: 1 2 3 4 5 6 7

idx: 0 2 4 6 1 3 5

위 idx를 사용해서 각 쿼리에 대해 i-1 <= idx <= j-1 를 만족하는 k번째 숫자를 for문을 이용해서 구하면 되니,

첫 정렬 시간복잡도 O(NlgN), 모든 쿼리에 대한 시간복잡도 O(NQ)를 더해주면 O(NlgN + NQ)로 pypy3에서 (python3 TLE) AC를 받게 됩니다.

https://www.acmicpc.net/source...

머지 소트를 이용하지 않고도 매우 쉽게 맞을 수 있는 문제여서 문제의 난이도를 낮추던가, pypy3의 시간을 더 팽팽하게 잡아야 하지 않을까 싶습니다. 고수님들의 의견이 궁금해요!

djs100201   2년 전

정해의 시간복잡도는 O(Q(logN)^2)일것 같긴 합니다
시간을 줄이는게 좋아보이긴 합니다.

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