MKTHNUM - K-th Number

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.

That is, given an array a[1 ... n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i ... j] segment, if this segment was sorted?"

For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2 ... 5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.


The first line of the input contains n — the size of the array, and m — the number of questions to answer (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000).

The second line contains n different integer numbers not exceeding 10^9 by their absolute values — the array for which the answers should be given.

The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1) and represents the question Q(i, j, k).

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3


For each question output the answer to it — the k-th number in sorted 
a[i ... j] segment. 

Note : naive solution will not work!!!

hide comments
leafbebop: 2017-05-31 05:16:35

Note: sometimes it is not the algorithms blocks you from AC, but the I/O speed.
For golang user, read this topic:!topic/golang-nuts/W08rFBcHKbc
Other language may have similar issues. Try Buffered I/O.

Oh, and also, minimize function calls, of course.

Last edit: 2017-05-31 05:20:11
mddaud001: 2017-05-20 21:26:13

Trying to solve from last week
Merge sort tree + Compression + Binary_search AC :-)

rihaz_zahir: 2017-02-15 20:12:33

why array compression with sqrt decomposition + segment tree is giving tle?

crazymax: 2016-10-31 15:01:26

Mo+ordered_set_tree (complexity with - Q*sqrt(N)*log(N)+N*sqrt(N)) solution gives TLE. :(

Ravi kumar: 2016-10-25 15:57:06

Increase time limit for java. there is not even a single accepted solution.
using (n+m)*logn complexity algo.

Edit: i tried the same algo in C++ and it passed. you need to increase time limit for java.

Last edit: 2016-10-25 16:17:58
i_m_a_coder: 2016-09-07 22:35:48

i did it using vectors and iterators bt getting wrong answer!!!

tamionv: 2016-08-27 03:56:22

I think I'm the first one to solve it in O((N+Q) * sqrt(N)) :)

kiwi1995: 2016-07-21 08:08:37

learnt a lot from this problem...:D

akshayv3: 2016-07-16 11:01:50

Solved using Persistent Segment trees and execution time was 0.5 s and the same solution times out in c++ 4.3.2

shiva_swag1: 2016-06-24 21:10:51

binary search +persistence segment tree..
binary search over -10^9 to +10^9 got tle..
binary search over elements of arr got ac..
log(2*10^9) factor proved very costly than log(10^5)... :-)

Added by:~!(*(@*!@^&
Time limit:0.115s-0.667s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Northeastern Europe 2004 Northern Subregion