Блог пользователя Schrodinger_Bit

Автор Schrodinger_Bit, 17 месяцев назад, По-английски

Recently I was solving CSES-Towers . In this problem I firstly tried a solution using multiset O(nlogn) solution resulted in TLE. Then I optimized the solution with vector which also had a O(nlogn) complexity. I know solution with vector is the efficient one. But the other solution has also O(nlogn) complexity. Why it didn't work? Am I missing something ?

Solution with multiset :

#include<bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(v) v.begin(), v.end()
 
int n,x;
multiset<int> s;
void solve(int cs){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x;
        auto it=upper_bound(all(s),x);
        s.insert(x);
        if(it!=s.end()) s.erase(s.find(*it));
 
    }
    cout << s.size() << endl;
    
}    
signed main(){
    fastio;
    int T=1,cs=0;
    //cin >> T;
    while(T--) solve(++cs);
}

Solution with vector :

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

 
 
int n,x;
vector<int> s;
void solve(int cs){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x;
        auto it=upper_bound(all(s),x);
        if(it==s.end()) s.pb(x);
        else s[it-s.begin()]=x;
 
    }
    cout << s.size() << endl;
    
}   
signed main(){
    fastio;
    int T=1,cs=0;
    //cin >> T;
    while(T--) solve(++cs);
}
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
17 месяцев назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

At here : auto it=upper_bound(all(s),x);

It is O(n),actually.

Use s.upper_bound(x) instead

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thanks a lot.

    It worked out. I didn't know about this.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi, I am curious to know how is auto it=upper_bound(all(s),x); O(n) here?

    from what I can see in the internal implementation, it uses __upper_bound() function which has a similar implementation to binary search:

    template<typename _ForwardIterator, typename _Tp, typename _Compare>
        _ForwardIterator
        __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
    		  const _Tp& __val, _Compare __comp)
        {
          typedef typename iterator_traits<_ForwardIterator>::difference_type
    	_DistanceType;
    
          _DistanceType __len = std::distance(__first, __last);
    
          while (__len > 0)
    	{
    	  _DistanceType __half = __len >> 1;
    	  _ForwardIterator __middle = __first;
    	  std::advance(__middle, __half);
    	  if (__comp(__val, __middle))
    	    __len = __half;
    	  else
    	    {
    	      __first = __middle;
    	      ++__first;
    	      __len = __len - __half - 1;
    	    }
    	}
          return __first;
        }