Cod sursa(job #2676566)

Utilizator Gliumarin negai Gliu Data 24 noiembrie 2020 16:46:47
Problema Subsir crescator maximal Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
//#include <iostream>
#include <fstream>

using namespace std;
typedef long long ll;

ifstream cin("scmax.in");
ofstream cout("scmax.out");
const ll NMAX=100009;
ll v[NMAX],q[NMAX],n,lem,p[NMAX],s[NMAX];

void read(){
	cin >>n;
	for(int i=1;i<=n;i++)cin>>v[i];
}

int bin(int k,int l,int r){
	int mid=(l+r)/2;
	
	if(l==r){
		if(r>lem)q[++lem+1]=2000000020;
		q[l]=k;
		return l;
	}else if(k<q[mid]) return bin(k,l,mid);
	else if(k>q[mid])return bin(k,mid+1,r);
}

int solve(){
	int i;
	lem=0;
	q[1]=v[1];
	for(i=1;i<=n;i++)
	   p[i]=bin(v[i],1,lem+1);
}

void afis(){
	int i,K=n;
	for(i=lem;i;i--){
		while(p[K] !=i)K--;
		s[i]=v[K];
	}
	
	for(i=1;i<=lem;i++)cout<<s[i]<<" ";
}

int main(){
read();
solve();
cout<<lem<<"\n";
afis();
return 0;
}