Help me debug MKTHNUM-spoj please
Разница между en1 и en2, 5 символ(ов) изменены
Hello, I have tried a lot to solve [MKTHNUM-spoj](https://www.spoj.com/problems/MKTHNUM/). 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 :'( .↵
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;↵
}↵
~~~~~↵


История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)