Revision en3, by Ahnaf.Shahriar.Asif, 2018-07-04 17:20:41

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))2) . 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;
}


#### History

Revisions Rev. Lang. By When Δ Comment
en3 Ahnaf.Shahriar.Asif 2018-07-04 17:20:41 79
en2 Ahnaf.Shahriar.Asif 2018-07-04 17:15:17 5 Tiny change: '\n } \n return 0;\' -> '\n } \n return 0;\'
en1 Ahnaf.Shahriar.Asif 2018-07-04 17:14:21 1770 Initial revision (published)