kmin > 문제은행

본문 바로가기


실전대비 Level5

1484 : kmin

제한시간: 2000 ms    메모리제한: 64 MB
해결횟수: 14 회    시도횟수: 184 회   



서로다른 정수로 이뤄진 배열 a[1..n]이 주어졌을 때, 질문 Q(i, j, k)을 연속적으로 처리하는 프로그램을 작성하라.

 

여기서 Q(i, j, k)라는 것은 다음과 같다: a[i...j]의 숫자를 정렬해서 나열하였을 경우의 k번째 숫자는 무엇인가?

 

예를 들어, a=(1, 5, 2, 6, 3, 7, 4) 라고 하자.
Q(2, 5, 3)이 들어왔을 경우 a[2...5]는 (5, 2, 6, 3)이며, 이를 정렬하였을 경우에는 (2, 3, 5, 6)이 된다. 여기서 k는 3이고 우리가 구하고자 하는 3번째 숫자는 5가 된다. 따라서 배열 a에 대한 Q(2, 5, 3)의 답은 5다.


입력의 첫 번째 줄에는 배열 a의 원소의 개수 N과 Q(i, j, k)의 개수 M이 입력된다(1≤N≤100,000, 1≤M≤5,000).
두 번째 줄에는 N개의 서로 다른 정수가 입력되며 이 숫자들의 절대값은 109를 넘지 않는다.
다음의 M개의 줄에는 Q(i, j, k)의 i, j, k가 입력된다. (1≤i≤j≤n, 1≤k≤j-i+1).


Q(i j k)의 질문이 입력된 순서대로 이에 대한 답을 출력한다.

[Copy]
7 3 
1 5 2 6 3 7 4 
2 5 3 
4 4 1 
1 7 3
[Copy]
5
6
3





Northeastern Europe 2004, Northern Subregion, poj 2104

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.