Cod sursa(job #2891080)

Utilizator DooMeDCristian Alexutan DooMeD Data 17 aprilie 2022 14:34:27
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 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];
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;
	vector<int> temp;
	for(int i=1; i<=n; i++) {
		f >> v[i];
		temp.emplace_back(v[i]);
	}
	sort(temp.begin(), temp.end());
	temp.erase(unique(temp.begin(), temp.end()), temp.end());
	
	for(int i=1; i<=n; i++) {
		int norm = lower_bound(temp.begin(), temp.end(), v[i]) - temp.begin() + 1;
		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(v[pos]);
		pos = ant[pos];
	}
	g << dq.size() << "\n";
	while(!dq.empty()) {
		g << dq.front() << " ";
		dq.pop_front();
	}
	return 0;
}