Cod sursa(job #2891083)

Utilizator DooMeDCristian Alexutan DooMeD Data 17 aprilie 2022 14:43:11
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <stdio.h>
#include <ctype.h>	
 
/** Funcţiile necesare parsării fişierului de intrare **/
FILE *_fin;
int _in_loc; char _in_buff[4096];	
 
void read_init(const char* nume) // Apelaţi această funcţie la începutul funcţiei <main>	
{
	_fin = fopen(nume, "r");
	_in_loc = 4095;	
}	
 
char read_ch()	
{
	++_in_loc;
	if (_in_loc == 4096) {
		_in_loc = 0;
		fread(_in_buff, 1, 4096, _fin);
	}
	return _in_buff[_in_loc];	
}	
 
int read_u32() // Apelaţi această funcţie pentru a citi un număr ce se încadrează în categoria <unsigned int>	
{
	int u32 = 0; char c;
	while (!isdigit(c = read_ch()) && c != '-');
	int sgn = 1;
	if (c == '-') {
		sgn = -1;
	} else {
		u32 = c - '0';
	}
	while (isdigit(c = read_ch())) {
		u32 = u32 * 10 + c - '0';
	}
	return u32 * sgn;	
}

#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() {
	read_init("scmax.in");
	ofstream g("scmax.out");
	
	n = read_u32();
	vector<int> temp;
	for(int i=1; i<=n; i++) {
		v[i] = read_u32();
		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;
}