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