시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1536 MB | 400 | 82 | 46 | 14.330% |
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
l r k
: S를 A의 l번째 수부터 r번째 수까지 수로 이루어진 오름차순으로 정렬된 집합(중복을 허용하지 않음)이라고 했을 때, k번째 수를 출력한다. 만약, k번째 수가 존재하지 않으면 -1을 출력한다.수열의 인덱스는 1부터 시작한다.
첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)
넷째 줄부터 M개의 줄에는 쿼리를 만드는 정보인 ai, bi, ci, di, ki가 한 줄에 하나씩 주어진다. (0 ≤ ai, bi, ci, di ≤ N, 1 ≤ ki ≤ N)
각각의 쿼리 li, ri는 다음과 같이 만든다.
먼저, i-1번째 쿼리의 정답을 ansi-1이라고 한다. (0번째 쿼리의 정답 ans0 = 0)
만약, li > ri 이면 li와 ri를 바꾼다.
각각의 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.
4 3 2 1 2 4 0 1 0 3 2 2 0 0 3 4 1 2 1 3 2 2 0 0 3 3
2 -1 2 3
10 9 10 6 3 8 4 9 6 4 10 10 0 2 0 9 3 1 9 1 3 3 1 8 1 0 3 1 2 1 7 2 1 6 1 2 3 1 4 1 3 1 1 6 1 6 1 1 4 1 8 1 1 9 1 3 3 1 9 1 2 1
6 9 10 4 6 3 10 4 6 4