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

0 votes

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;
}
Jun 29, 2022 in C++ by Damon
• 4,960 points
317 views

No answer to this question. Be the first to respond.

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.

Related Questions In C++

0 votes
0 answers

Difference between upper_bound and lower_bound in stl

I was looking at how the upper bound and lower bound algorithms operate in stl on these pages: lower bound, upper bound, and it's documented the same way on these pages: lower bound, upper bound, and it's documented the same way on these pages: lower bound, upper bound, and it'  upper bound, lower bound Looking at the code from the links, they appear to perform the same thing to me, with the exception of the following lines  lower_bound (line 10): if (*it<val) { ...READ MORE

Jul 5, 2022 in C++ by Nicholas
• 7,760 points
1,014 views
0 votes
0 answers

What is the difference between std::list<std::pair> and std::map in C++ STL?

What distinguishes std::list<std::pair> from std::map? Does the ...READ MORE

Aug 17, 2022 in C++ by Nicholas
• 7,760 points
373 views
0 votes
1 answer

What is the difference between std::__gcd and std::gcd?

I done some research about this. The ...READ MORE

answered Jun 10, 2022 in C++ by Damon
• 4,960 points
1,513 views
0 votes
0 answers

Difference between 'new operator' and 'operator new'?

What is difference between "new operator" and ...READ MORE

Jun 15, 2022 in C++ by Nicholas
• 7,760 points
225 views
0 votes
1 answer

C++ code file extension? What is the difference between .cc and .cpp [closed]

GNU GCC recognizes all of the following ...READ MORE

answered Jun 21, 2022 in C++ by Damon
• 4,960 points
1,323 views
0 votes
1 answer

Difference between Turbo C++ and Borland C++ compiler [closed]

I will try my best to respond, ...READ MORE

answered Jun 21, 2022 in C++ by Damon
• 4,960 points
920 views
0 votes
1 answer

Syntax of priority queue

We must first include the queue header file in order to establish a priority queue in C++. #include <queue> Once we import this file, we ...READ MORE

answered May 31, 2022 in C++ by Damon
• 4,960 points
388 views
0 votes
1 answer

Sorting a vector of custom objects

A simple example using std::sort struct MyStruct { ...READ MORE

answered Jun 1, 2022 in C++ by Damon
• 4,960 points
1,108 views
0 votes
1 answer

lower_bound == upper_bound

Lower bound: the initial greater-or-equal element. Upper bound: ...READ MORE

answered Jun 21, 2022 in C++ by Damon
• 4,960 points
851 views
0 votes
1 answer

Comparison of C++ STL collections and C# collections

This is what I know Array - C ...READ MORE

answered Jun 9, 2022 in C# by rajiv
• 1,620 points
481 views
webinar REGISTER FOR FREE WEBINAR X
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP