Cod sursa(job #474561)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 4 august 2010 10:05:17
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<algorithm>
using namespace std;
#define N_MAX 100005

typedef pair <int,int> p;
p arb[257*4+10];
int n,i,j;
int a[N_MAX];
int dp[N_MAX];

void update(int nod,int st,int dr,int poz,p x)
{
	if(st==dr)
	{
		arb[nod]=x;
		return ;
	}
	int md=(st+dr)>>1;

	if(poz<=md)
		update((nod<<1),st,md,poz,x);
	if(md<poz)
		update((nod<<1)+1,md+1,dr,poz,x);

	if(arb[nod].first<arb[(nod<<1)].first)
		arb[nod]=arb[(nod<<1)];
	if(arb[nod].first<arb[(nod<<1)+1].first)
		arb[nod]=arb[(nod<<1)+1];
}

p query(int nod,int st,int dr,int a,int b)
{
	if(a<=st&&dr<=b)
	{
		return arb[nod];
	}
	int md=(st+dr)>>1;

	p ST,DR;	ST=DR=p(0,n+1);

	if(a<=md)
		ST=query((nod<<1),st,md,a,b);
	if(md<b)
		DR=query((nod<<1)+1,md+1,dr,a,b);

	if(ST.first>DR.first)
		return ST;
	return DR;
}

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	scanf("%d",&n);

	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);

	for(i=0;i<((257<<2)+9);i++)
		arb[i]=p(0,n+1);
	
	for(i=n;i>0;i--)
	{
		dp[i]=1;
		p j=query(1,0,257,a[i]+1,257);

		dp[i]=dp[j.second]+1;
		update(1,0,257,a[i],p(dp[i],i));
	}

	i=max_element(dp+1,dp+n+1)-dp;
	
	printf("%d\n%d ",dp[i],a[i]);
	int ind=i;
	
	for(;i<=n;i++)
		if(dp[ind]==dp[i]+1&&a[ind]<a[i])
		{
			printf("%d ",a[i]);
			ind=i;
		}

	return 0;
}