Cod sursa(job #1181271)

Utilizator sorin2kSorin Nutu sorin2k Data 2 mai 2014 12:52:37
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<fstream>
#include<cstdlib>
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int v[100001], sorted[100001], norm[100001], aib[100001], parent[100001], dp[100001], Q[100001];
int n, p;

inline int nr_de_0(int x) {
	int nr = 0;
	while(x % 2 == 0) {
		x >>= 1;
		nr++;
	}
	return nr;
}

inline int pow_doi(int exp) {
	int rez = 1, i;
	for(i = 1; i <= exp; i++) {
		rez <<= 1;
	}
	return rez;
}

int compar(const void *a, const void *b) {
	return *(int *)a - *(int *)b;
}

int caut_bin(int val) {
	int l = 1, r = n, mid, ans = -1;
	while(l <= r) {
		mid = l + (r-l) / 2;
		if(sorted[mid] >= val) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return ans;
}

int aib_query(int poz) {
	int maxim = 0;
	while(poz > 0) {
		if(dp[aib[poz]] > dp[maxim]) maxim = aib[poz];
		poz -= pow_doi(nr_de_0(poz));
	}
	return maxim;
}

// am modificat dp[i] in main
// pun pe pozitia norm[i] (+ toate mai mari din aib) valoarea i (daca dp[i] > dp[aib[poz]])
void aib_update(int i) {
	int poz = norm[i];
	while(poz <= n) {
		if(dp[aib[poz]] < dp[i]) aib[poz] = i;
		poz += pow_doi(nr_de_0(poz));
	}

}

int main() {
	int i, p, last = 0;

	fin >> n;
	for(i = 1; i <= n; i++) {
		fin >> v[i];
		sorted[i] = v[i];
	}
	qsort(sorted+1, n, sizeof(int), compar);

	// construiesc vectorul normalizat
	for(i = 1; i <= n; i++) {
		norm[i] = caut_bin(v[i]);
	}

	for(i = 1; i <= n; i++) {
		p = aib_query(norm[i] - 1);

		dp[i] = 1 + dp[p];
		parent[i] = p;
		if(dp[i] > dp[last]) last = i;

		aib_update(i);
	}

	while(dp[last] != 0) {
		Q[++Q[0]] = v[last];
		last = parent[last];
	}

	fout << Q[0] << "\n";
	for(i = Q[0]; i > 0; i--) fout << Q[i] << " ";
	return 0;
}