K-th Minimum Number

View as PDF

Submit solution

Points: 17
Time limit: 1.5s
Memory limit: 512M

Problem type

Given an array A of N numbers, you need to answer Q queries of the form l' r' k', where you output the k^\text{th} minimum number in the range [l, r].

Constraints

1 \le N, Q \le 200\,000

1 \le l \le r \le N

1 \le k \le r-l+1

1 \le A_i \le 10^9

Input Specification

The first line will contain N and Q, the number of elements in the array and the number of queries.

The second line will contain N space-separated integers, the elements of A.

The next Q lines will contain a query defined above.

Note that this problem will be online enforced, meaning that input will be given in an encrypted format. To encrypt the data, the values l, r, k in queries will be given as l' = l \oplus \text{lastAns}, r' = r \oplus \text{lastAns}, and k' = k \oplus \text{lastAns}, where \oplus denotes the bitwise XOR operation. Note that \text{lastAns} at any time is defined as the answer to the latest query. If no queries have occurred so far, \text{lastAns} = 0.

Output Specification

Output Q lines, the answers to the queries.

Sample Input (Encrypted)

5 5
1 3 4 5 1
1 5 3
0 6 0
6 6 4
5 6 6
2 6 6

Sample Input (Unencrypted)

5 5
1 3 4 5 1
1 5 3
3 5 3
3 3 1
1 2 2
1 5 5

Sample Output

3
5
4
3
5

Comments

There are no comments at the moment.