Why I am getting TLE when i use my upper bound function for stacks problem

general
,
1

why I am getting TLe here ? when I use stl upper bound it does not give me TlE

#include <bits/stdc++.h>

using namespace std;

#define PB push_back

typedef long long ll;

const ll N = 1e5 + 10;

ll n;

ll stacks[N];

inline ll binary_search(ll key, vector tops)

{

ll low = -1;

ll high = tops.size();

int counter = 0;

while (high - low > 1)

{

    ll mid = (low + high) / 2;

    counter++;

    if (tops[mid] <= key)

    {

        low = mid;

    }

    else

        high = mid;

}

return low+1;

}

int main()

{

// cout<<binary_search(41);

ll t;

cin >> t;

while (t--)

{

    cin >> n;

    vector<ll> tops;

    for (ll i = 0; i < n; i++)

    {

        cin >> stacks[i];

    }

    for (ll i = 0; i < n; i++)

    {

        ll idx = binary_search(stacks[i] , tops) ;

        // ll idx = upper_bound(tops.begin(), tops.end(), stacks[i]) - tops.begin();

        if (idx == tops.size())

            tops.PB(stacks[i]);

        else

            tops[idx] = stacks[i];

    }

    cout<<tops.size()<<" ";

    for(auto i : tops)

        cout<<i<<" ";

    cout<<'\n';

}

}Preformatted text

2

try ‘mid = (low+high+1)/2’, maybe an off-by-one error.

Its also better to use the stl functions when you can rather than implementing yours lol

1 Like
3

yeah , you are right , I better use stl functions . It still gives me tile after mid =(low+high+1)/2

4

binary search has lot of implementation variations be careful It might get into inf loop.
I usually prefer
while(l<=h){
if(cond)
h=m-1;
else
l=m+1
}

1 Like