In this problem?We should write time complexity O(N log2(N));But i didn't understand solution proof.
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define ppb pop_back
#define sz size()
#define ss second
#define ff first
#define N 200001
using namespace std;
ll _, x, n, a[N];
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
vector <ll> v;
v.pb(a[1]);
for(int i = 2; i <= n; i++){
auto t = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
if(t == v.sz) v.pb(a[i]);
else{
v[t] = a[i];
}
}
// for(auto i : v) cout << i << ' ';
cout << v.sz;
}
This code gets accepted.
cp-algorithms (the array
v
in your code corresponds to the arrayd
in the explanation)