Cod sursa(job #710445)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 9 martie 2012 18:36:49
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>

#define MAXN 100010

long arb[MAXN], v[100010], n, i, fr[MAXN], sol, af, poz, S[MAXN], h[MAXN];

inline long max(long a, long b) {
	if (a < b && b != 2000000000) 
		return b; 
	return a;
}

void parc(long st, long dr, long pz) {
	if (st == dr) {
		if (arb[pz] >= v[i]) {
			arb[pz] = v[i];
			h[i] = st;
			af = 1;
			if (fr[st] == 0) {
				++sol;
				fr[st] = 1;
			}			
		}
		return;
	}
	
	parc(st, (st + dr) / 2, pz * 2);
	arb[pz] = max(arb[pz * 2], arb[pz * 2 + 1]);
	if (af == 1) return;	
	parc((st + dr) / 2 + 1, dr, pz * 2 + 1);
	arb[pz] = max(arb[pz * 2], arb[pz * 2 + 1]);
	if (af == 1) return;	
}

int main() {
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) scanf("%ld", &v[i]);
	for (i = 1; i < 10000; ++i) arb[i] = 2000000000;
	for (i = 1; i <= n; ++i) {
		af = 0;
		parc(1, n, 1);
	}
	
	printf("%ld\n", sol);
	long caut = sol;
	for (i = n; i >= 1; --i) {
		if (caut == h[i]) {
			S[++S[0]] = v[i];
			--caut;
		}
	}
	for (i = S[0]; i >= 1; --i) printf("%ld ", S[i]);
	return 0;
}