Hello, I have tried a lot to solve MKTHNUM-spoj. For solving this , I have slightly changed the problem statement, it goes like this :

you are asked to find a number such that there are k-1 numbers less than that in range [l...r]

Then I made a merge sort tree and sorted the initial array and Binary Searched it. My time complexity is : O((log2(n))²) . I am getting Runtime Error in case 11 (i think). But couldn't find the bug :'( .

Updt: Now I am getting wrong answer. first 14 test cases ran smmothly

here goes my code :

#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;

const int N = 100099;
vector<int>tree[N*3];
int ara[N+12];

void build(int at ,int l,int r)
{
    if(l == r){
	tree[at].push_back(ara[l]);
	return;
    }
    int mid = (l+r)/2;
    build(at*2,l,mid);
    build(at*2+1,mid+1,r);
	
    merge(all(tree[at*2]),all(tree[at*2+1]),back_inserter(tree[at]));
}

int query(int at,int L,int R,int l,int r,int indx)
{
    if(l > R or r < L)return 0;
    if(L >= l and r >= R){
	int pp = upper_bound(all(tree[at]),ara[indx])-tree[at].begin();
	return pp;
    }
    int mid = (L+R)/2;
    return query(at*2,L,mid,l,r,indx) + query(at*2+1,mid+1,R,l,r,indx);
}

int main()
{
    int n,q,l,r,k;
    scanf("%d%d",&n,&q);
    for(int i= 1; i <= n;i++){
	scanf("%d",&ara[i]);
    }
    build(1,1,n);
    sort(ara+1,ara+1+n);
    while(q--){
	scanf("%d%d%d",&l,&r,&k);
	int high = n,low = 1,mid,ans = -1;
	int cnt = 0;
	while(low <= high){
	    mid = (low+high)/2;
	    int pp = query(1,1,n,l,r,mid);
	    if(k <= pp){
		ans = mid;
		high = mid-1;
	   }
	   else low = mid+1;
	}
    printf("%d\n",ans);
    }	
    return 0;
}