Cod sursa(job #332452)

Utilizator cotofanaCotofana Cristian cotofana Data 17 iulie 2009 22:05:02
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 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) {
		arb[node]=pos;
		return ;
	}
	
	int m=(l+r)/2;
	if (pos<=m) update(2*node, l, m);
	else update(2*node+1, m+1, r);
	
	if (v[arb[2*node]]<v[pos+1] && v[arb[2*node+1]]<v[pos+1])
		if (best[arb[2*node]]>best[arb[2*node+1]]) arb[node]=arb[2*node];
		else arb[node]=arb[2*node+1];
	else if (v[arb[2*node]]<v[pos+1]) arb[node]=arb[2*node];
	else if (v[arb[2*node+1]]<v[pos+1]) arb[node]=arb[2*node+1];
	else arb[node]=0;
}

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]);
	v[n+1]=INF;
	
	best[1]=1;
	prec[1]=-1;
	pos=1;
	update(1, 1, n);
	for (i=2; i<=n; ++i) {
		in=arb[1];
		
		if (!in)
			best[i]=1,
			prec[i]=-1;
		else
			best[i]=best[in]+1,
			prec[i]=in;
		
		pos=i;
		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;
}