Cod sursa(job #492152)
/*
* File: main.cpp
* Author: bitone
*
* Created on October 13, 2010, 3:58 PM
*/
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define MAX_N 100011
using namespace std;
/*
*
*/
int N;
int v[MAX_N], w[MAX_N], l[MAX_N], index[MAX_N], f[MAX_N], aib[MAX_N];
inline int Update( int x, int y )
{
for( ; x <= N; x+=( x & -x ) )
if( l[aib[x]] < l[y] )
aib[x]=y;
}
inline int Query( int x )
{
int index=0;
for( ; x; x-=( x & -x ) )
if( l[aib[x]] > l[index] )
index=aib[x];
return index;
}
inline void output( ostream& out, int index )
{
if( index )
{
output( out, f[index] );
out<<v[index]<<' ';
}
}
int main( void )
{
int *new_end;
int i, maxindex=0;
ifstream in( "scmax.in" );
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 );
new_end=unique( w+1, w+N+1 );
for( i=1; i <= N; ++i )
if( v[i] == v[i-1] )
index[i]=index[i-1];
else index[i]=lower_bound( w+1, new_end, v[i] )-w+1;
for( i=1; i <= N; ++i )
{
f[i]=Query(index[i]-1);
l[i]=1+l[f[i]];
Update( i, index[i] );
if( l[i] > l[maxindex] )
maxindex=i;
}
ofstream out( "scmax.out" );
out<<l[maxindex]<<'\n';
output( out, maxindex );
out<<'\n';
}