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);
}