Cod sursa(job #2577374)

Utilizator valen.valentinValentin Valeanu valen.valentin Data 9 martie 2020 09:46:40
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>

#define SZ(x) ((int)(x.size()))

#define fst first
#define snd second
#define pb push_back
#define nmax 100010

using namespace std;

typedef pair<int, int> pii;

int n, n_size;
int a[nmax], dp[nmax], aib[nmax], p_dp[nmax], pred[nmax];
vector <int> p;

unordered_map <int, int> mp;

inline int lsb(int x) { return x & (-x); }

void update(int pos, int val, int ipos)
{
	for (int i = pos; i <= n_size; i += lsb(i)) 
		if (val > aib[i]) {
			
			aib[i] = val; p_dp[i] = ipos;
		}
}

pii query(int pos)
{
	pii ans = { 0, -1 };
	
	for (int i = pos; i >= 1; i -= lsb(i))
		if (aib[i] > ans.fst) ans = { aib[i], p_dp[i] };
	
	return ans;
}

int main()
{	
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++) {
		
		scanf("%d", &a[i]); p.pb(a[i]); p_dp[i] = -1;
	}
	
	sort(p.begin(), p.end());
	
	n_size = 0;
	
	mp.reserve(1024);
	mp.max_load_factor(0.25);
	
	for (int i = 0; i < SZ(p); i++)
		if (i == 0 || p[i] != p[i - 1]) mp[p[i]] = ++n_size;
	
	for (int i = 1; i <= n; i++) {
		
		int idx = mp[a[i]];
		
		pii res = query(idx - 1);
		
		dp[i] = res.fst + 1;
		pred[i] = res.snd;
		
		update(idx, dp[i], i);
	}
	
	int idx = 0;
	int best = 0;
	
	vector <int> ans;
	
	for (int i = 1; i <= n; i++)
		if (dp[i] > best) { best = dp[i]; idx = i; }
		
	while (idx != -1) { ans.pb(a[idx]); idx = pred[idx]; }
	
	printf("%d\n", best);
	
	for (int i = SZ(ans) - 1; i >= 0; i--) printf("%d ", ans[i]);
	
	return 0;
}