Cod sursa(job #2891086)

Utilizator DooMeDCristian Alexutan DooMeD Data 17 aprilie 2022 14:51:21
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;

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

int best[nmax+5], bef[nmax+5], a[nmax+5];
int v[nmax+5], n, len[nmax+5], ant[nmax+5];

void update(int pos, int val, int ind) {
	for(int i=pos; i<=n; i+=lsb(i)) 
		if(val > best[i]) { 
			best[i] = val;
			bef[i] = ind;
		}
}

pair<int, int> query(int pos) {
	pair<int, int> temp = make_pair(0, 0);
	for(int i=pos; i>=1; i-=lsb(i)) 
		if(best[i] > temp.first) {
			temp.first = best[i];
			temp.second = bef[i];
		}
	return temp;
}

int main() {
	ifstream f("scmax.in");
	ofstream g("scmax.out");
	
	f >> n;
	for(int i=1; i<=n; i++) {
		f >> v[i];
		a[i] = v[i];
	}
	sort(v+1, v+n+1);
	map<int, int> m;
	for(int i=1; i<=n; i++) {
		m[v[i]] = 0;
		m[v[i]] = m.size();
	}
	for(int i=1; i<=n; i++) {
		int norm = m[a[i]];
		pair<int, int> w = query(norm-1);
		len[i] = w.first + 1;
		ant[i] = w.second;
		update(norm, len[i], i);
	}
	int mx = 0, indmx;
	for(int i=1; i<=n; i++) 
		if(len[i] > mx) {
			mx = len[i];
			indmx = i;
		}
	deque<int> dq;
	int pos = indmx;
	while(pos != 0) {
		dq.emplace_front(a[pos]);
		pos = ant[pos];
	}
	g << dq.size() << "\n";
	while(!dq.empty()) {
		g << dq.front() << " ";
		dq.pop_front();
	}
	return 0;
}