Cod sursa(job #332449)

Utilizator cotofanaCotofana Cristian cotofana Data 17 iulie 2009 21:53:05
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#define MAXN 100001
#define MAXARBN 1<<20
#define INF 2000000001

int n, v[MAXN], best[MAXN], prec[MAXN], ct, sol[MAXN];
int arb[MAXARBN], start, end, pos;

void update(int node, int l, int r) {
	if (l==r) {
		if (l<pos && v[l]<v[pos]) arb[node]=l;
		else arb[node]=0;
		/*if (l<pos) arb[node]=best[l];
		else arb[node]=0;*/
		return ;
	}
	
	int m=(l+r)/2;
	update(2*node, l, m);
	update(2*node+1, m+1, r);
	
	if (best[arb[2*node]]>best[arb[2*node+1]]) arb[node]=arb[2*node];
	else arb[node]=arb[2*node+1];
	/*if (arb[2*node]>arb[2*node+1]) arb[node]=arb[2*node];
	else arb[node]=arb[2*node+1];*/
}

int main() {
	int i, in;
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	scanf("%d\n", &n);
	for (i=1; i<=n; ++i) scanf("%d\n", &v[i]);
	
	best[1]=1;
	prec[1]=-1;
	for (i=2; i<=n; ++i) {
		pos=i;
		update(1, 1, n);
		
		in=arb[1];
		if (!in)
			best[i]=1,
			prec[i]=-1;
		else
			best[i]=best[in]+1,
			prec[i]=in;
	}
	
	pos=n+1;
	v[n+1]=INF;
	update(1, 1, n);
	in=arb[1];
	ct=0;
	while (in>0)
		sol[++ct]=v[in],
		in=prec[in];
	
	printf("%d\n", ct);
	for (i=ct; i; --i) printf("%d ", sol[i]);
	printf("\n");
	
	return 0;
}