Finding median of sub arrays taking too much time I'm trying to solve a programming challenge where I have to find the median of given subarrays of an array. I have used std::vector's n_th element for this. But the evaluator fails some test cases as "time limit exceeded".

#include &lt;iostream&gt;
#include &lt;bits/stdc++.h&gt;

using namespace std;

/*
In
6
2 4 5 3 1 6
3
1 6
2 4
3 3

Out
3
4
5

*/

int get_ceil(int length)
{
    if (length % 2 == 0)
    {
        return length/2;
    }
    else
    {
        return (length+1)/2;
    }

}

int get_median_of_subarray(std::vector&lt;int&gt; &amp; full_array, int lo, int hi)
{

    std::vector&lt;int&gt;::const_iterator begin = full_array.begin() + lo;
    std::vector&lt;int&gt;::const_iterator end = full_array.begin() + hi + 1;
    std::vector&lt;int&gt; sub_array(begin, end);

    int median_pos = get_ceil(hi - lo + 1);
    std::nth_element (sub_array.begin(), sub_array.begin() + median_pos -1, sub_array.end());
    return sub_array[median_pos - 1];
}



int main()
{
    ios_base::sync_with_stdio(false);

    int array_size = 0;
    std::vector&lt;int&gt; input_array;

    cin &gt;&gt; array_size;

    for(int i = 0; i &lt; array_size; i++)
    {
        int x;
        cin &gt;&gt; x;
        input_array.push_back(x);
    }

    int query_size = 0;
    cin &gt;&gt; query_size;

    int lo = 0;
    int hi = 0;

    for(int i = 0; i &lt; query_size; i++)
    {
        cin &gt;&gt; lo &gt;&gt; hi;
        std::cout &lt;&lt; get_median_of_subarray(input_array, --lo, --hi) &lt;&lt; std::endl;
    }

    return 0;
}
Not related to performance, but never ever do this:

#include &lt;bits/stdc++.h&gt;

using namespace std;


For reference see these Q&amp;A at Stack Overflow:


Why should I not #include &lt;bits/stdc++.h&gt;?
Why is “using namespace std;” considered bad practice?