Can anybody explain this problem's solution proof?

Правка en1, от Halym2007, 2023-07-03 15:12:28

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Halym2007 2023-07-03 15:12:28 775 Initial revision (published)