Informatica Online Judge

  경품 추첨 #1 [1627 / 065B]

Time Limit(Test case) : 200 (ms)
Number of users who solved : 16   Total Tried : 23


The Champion of this Problem (C++) : gs17003 - 0ms / 371byte
My Best Submission (C++) : N/A

[JKJeong 2016]

Background

경곽이를 포함한 n명의 친구들은 경품추첨장소에서 줄을 서 있다.

이 곳의 추첨 방식은 특별하다.

n명의 사람들이 한 줄로 서 있으면, 각 사람들에게 수가 적힌 카드를 한 장씩 준다.

모든 사람이 받은 카드의 값은 서로 다르다.

추첨 방식은 다음과 같다.

a번째 사람부터 b번째 사람들이 가지고 있는 카드들 중에서 k번째로 작은 수의 카드를 가진 사람에게 선물을 준다.

예를 들어 5명의 사람들이 받은 카드가 다음과 같다고 가정하자.

5, 4, 3, 2, 1

a = 2 , b = 4 , k = 1 이라면

2번째 사람부터 4번째 사람까지 중 가장 낮은 수의 카드를 가진 사람이 선물을 받는다.

5, [4, 3, 2], 1

따라서 4번 사람이 2번 카드를 가지고 있으므로 선물을 받는다.

m번의 추첨을 할 때, 각 추첨에 대해서 선물을 받을 사람이 가진 카드의 번호의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 원소의 수 n과 m이 공백으로 구분되어 입력된다.

둘째줄에 n개의 원소가 공백으로 구분되어 입력된다.

다음 줄부터 m줄에 걸쳐서 각각 a, b, k의 값이 입력된다.

[Sub_Task Info]
#1 : 1 <= n <= 100,000 ; 1 <= m <= 2,000 ; 1 <= a < b <= n ; k = 1
#2 : 1 <= n <= 100,000 ; 1 <= m <= 2,000 ; 1 <= a < b <= n ; 1 <= k <= (b-a+1)
모든 원소는 서로 다른 정수이다.

Output

각 m번의 추첨에 대해서 당첨되는 사람이 가진 카드의 번호를 한 줄에 하나씩 출력한다.

IO Example

입력
5 1
5 4 3 2 1
2 4 1

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]