Halym2007's blog

By Halym2007, history, 16 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

cp-algorithms (the array v in your code corresponds to the array d in the explanation)