Difference between set upper bound and upper bound set begin set end stl

Question

I discovered that set.upper bound() was quicker than set.lower bound() (The latter gave Time Limit Exceeded). Why is this the case?

The following code returns Time Limit Exceeded.

int ind = *upper_bound(st.begin(), st.end(), mp[i], greater< int >());

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
# define ll  long long int
# define ld  long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
typedef priority_queue<ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<ll> maxheap;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void solve(){
    int n;
      cin>>n;
      set<int, greater<int>>st;
      st.insert(-1);
      map<int,int> mp;
      int p[2*n];
      char s[2*n];
        for(int i=0;i<2*n;i++)
      {
          cin>>s[i];
          if(s[i]=='+')
          st.insert(i);
          else
          {
              cin>>p[i];
              mp[p[i]]=i;
          }
     
      }
      for(int i=1;i<=n;i++)
      {
        
          int ind = *upper_bound(st.begin(), st.end(), mp[i], greater< int>());
          if(ind==-1||st.find(ind)==st.end())
          {
              // if (-) come before +
              cout<<"NO\n";
              return;
          }
          st.erase(ind);
          p[ind] = i;
          
      }
     
    // cout<<endl;
    stack<int>stc;
    for(int i=0;i<2*n;i++)
    {
        if(s[i]=='+')
        stc.push(p[i]);
        else
        {
            if(stc.top()==p[i])
            stc.pop();
            else
            {
                //if element not in order given in language
                cout<<"NO\n";
                return ;
            }
        }
    }
    cout<<"YES\n";
    for(int i=0;i<2*n;i++)
    {
        if(s[i]=='+')
        cout<<p[i]<<endl;
    }
    return;
}   


int  main()
{
    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif
      IOS
     int t = 1;
     //cin >> t;
     while(t--){
        solve();
     }
    return 0;
}

The same code with "set.upper_bound()" get executed within Time Limit.

int ind = *st.upper_bound(mp[i]);

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
# define ll  long long int
# define ld  long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
typedef priority_queue<ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<ll> maxheap;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void solve(){
    int n;
      cin>>n;
      set<int, greater<int>>st;
      st.insert(-1);
      map<int,int> mp;
      int p[2*n];
      char s[2*n];
        for(int i=0;i<2*n;i++)
      {
          cin>>s[i];
          if(s[i]=='+')
          st.insert(i);
          else
          {
              cin>>p[i];
              mp[p[i]]=i;
          }
     
      }
      for(int i=1;i<=n;i++)
      {
        
          int ind = *st.upper_bound(mp[i]);
          if(ind==-1||st.find(ind)==st.end())
          {
              // if (-) come before +
              cout<<"NO\n";
              return;
          }
          st.erase(ind);
          p[ind] = i;
          
      }
     
    // cout<<endl;
    stack<int>stc;
    for(int i=0;i<2*n;i++)
    {
        if(s[i]=='+')
        stc.push(p[i]);
        else
        {
            if(stc.top()==p[i])
            stc.pop();
            else
            {
                //if element not in order given in language
                cout<<"NO\n";
                return ;
            }
        }
    }
    cout<<"YES\n";
    for(int i=0;i<2*n;i++)
    {
        if(s[i]=='+')
        cout<<p[i]<<endl;
    }
    return;
}   


int  main()
{
    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif
      IOS
     int t = 1;
     //cin >> t;
     while(t--){
        solve();
     }
    return 0;
}

Answer 1

set::upper bound will search for value using the set's capability (logarithmic with regards to the size of the container).

For std::upper_bound, using non-LegacyRandomAccessIterators, like a std::sets iterators (that are LegacyBidirectionalIterators), the number of iterator increments is linear.