예전에 "정렬하기" 단계에 있었던 슬라이딩 윈도우 중앙값과 비슷한 상황이라고 생각합니다. 분할정복 단계에 있는 이유가 "K번째 숫자"라는 제목 때문이라고밖에 생각이 안 됩니다.

예전에 올린 글에 내용을 추가했습니다: https://www.acmicpc.net/board/...

가장 잘 알려진 해법은 "머지소트 트리를 만들고 이분탐색으로 쿼리를 해결"인 것 같은데, 정작 트리 단계부터 분할 정복 단계보다 밑에 있고, 이분 탐색은 더 밑에 있으며, 구간 트리는 거의 맨 밑에 있습니다. 이 문제보다 나중에 나오는 알고리즘으로 브루트포스 (?!!), BFS/DFS, 다익스트라 등이 있습니다. 꼭 분할정복만 써야 하느냐 하면 그것도 아닙니다. 분할 정복을 안 쓰는, 빠르고 간단한 O(NM) 풀이도 통과됩니다. (Pypy) (C++) 퀵셀렉으로 풀 수 있다면야 분할정복이겠지만, 범위가 세고 퀵셀렉이 무거워서 안 될 것으로 예상됩니다.

만에 하나 C++ 코드가 되는 이유가 데이터가 약해서일 수도 있으니, 아래 데이터를 추가해 주세요. 첨부한 코드로 만들었습니다. 하지만 제 컴퓨터에서도 1초 이내에 돌아갑니다.

https://www.dropbox.com/s/1um4... in

https://www.dropbox.com/s/ev3u... out

그 김에 다른 문제도 다시 링크하고자 합니다.

https://www.acmicpc.net/board/...