Cod sursa(job #736230)
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 100011
using namespace std;
int v[N_MAX], w[N_MAX], index[N_MAX], l[N_MAX], f[N_MAX], aib[N_MAX];
inline void Update(const int& N, int xIndex, const int& xValue)
{
for(; xIndex <= N; xIndex+=(xIndex & -xIndex) )
if(l[aib[xIndex]] < l[xValue])
aib[xIndex]=xValue;
}
inline int Query(int xIndex)
{
int m=0;
for(; xIndex; xIndex-=(xIndex & -xIndex) )
if(l[aib[xIndex]] > l[m])
m=aib[xIndex];
return m;
}
inline void Output(const int& x, ostream& out)
{
if(0 == f[x])
out<<v[x]<<' ';
else {
Output(f[x], out);
out<<v[x]<<' ';
}
}
int main()
{
int *iend;
int N, i, maxIndex=0;
ifstream in("scmax.in");
ofstream out("scmax.out");
in>>N;
copy(istream_iterator<int>(in), istream_iterator<int>(), v+1);
copy(v+1, v+N+1, w+1);
sort(w+1, w+N+1);
iend=w+N+1;
//iend=unique(w+1, w+N+1);
for(i=1; i <= N; ++i)
index[i]=lower_bound(w+1, iend, v[i])-w;
for(i=1; i <= N; ++i)
{
f[i]=Query(index[i]-1);
l[i]=l[f[i]]+1;
Update(N, index[i], i);
if(l[i] > l[maxIndex])
maxIndex=i;
}
out<<l[maxIndex]<<'\n';
Output(maxIndex, out);
out<<'\n';
return EXIT_SUCCESS;
}