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);
}
At here : auto it=upper_bound(all(s),x);
It is O(n),actually.
Use s.upper_bound(x) instead
Thanks a lot.
It worked out. I didn't know about this.
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:std::advance
is linear for non-random access iterators.https://cplusplus.com/reference/iterator/advance/
It has always baffled me that the STL allows you to do it the wrong way, is there really no way they could've put some guardrails around this? Specializing the upper_bound for set iterators or something like that...
The same thing for swapping sets, where you should do s1.swap(s2) instead of swap(s1, s2).
I get it now, thanks!