Cod sursa(job #2446091)

Utilizator ShayTeodor Matei Shay Data 6 august 2019 23:51:31
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

#define BUFFER_SIZE 1 << 17
#define NMAX ((int)1e5 + 5)

char buffer[BUFFER_SIZE];
int pos = BUFFER_SIZE;

int v[NMAX], dp[NMAX], prec[NMAX];

inline char next() {
	if (pos == BUFFER_SIZE) {
		fread(buffer, 1, BUFFER_SIZE, stdin);
		pos = 0;
	}
	return buffer[pos++];
}

inline int read() {
	int n = 0;
	char c = next();

	while (!('0' <= c && c <= '9')) {
		c = next();
	}

	while ('0' <= c && c <= '9') {
		n = (n << 3) + (n << 1) + (c - '0');
		c = next();
	}

	return n;
}

inline void print(int n) {
	char snum[65];
	int i = 0;

	do {
		snum[i++] = n % 10 + '0';
		n /= 10;
	} while (n);

	--i;

	while (i >= 0) {
		putchar(snum[i--]);
	}

	putchar(' ');
}

int binary_search(int value, int maxim) {
	int i, step;

	for (step = 1 ; step < maxim ; step <<= 1);
	for (i = 0; step ; step >>= 1) {
		if (i + step <= maxim && v[dp[i + step]] < value) {
			i += step;
		}
	}

	return i + 1;
}

int main() {
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);

	int n = read();

	for (int i = 1 ; i <= n ; ++i) {
		v[i] = read();
	}

	dp[1] = 1;
	int maxim = 1;

	for (int i = 2 ; i <= n ; ++i) {
		int pos = binary_search(v[i], maxim);
		maxim = std::max(maxim, pos);
		dp[pos] = i;
		prec[i] = dp[pos - 1];
	}

	print(maxim), putchar('\n');
	int pos = dp[maxim]; maxim = 0;

	std::vector<int> ans;
	while (pos) {
		dp[++maxim] = v[pos];
		pos = prec[pos];
	}

	for (int i = maxim ; i >= 1 ; --i) {
		print(dp[i]);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}