Cod sursa(job #936610)
#include <vector>
#include <cstdlib>
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 100011;
const int MAXBUFFER = 8193;
int idxBuffer = -1;
char buffer[MAXBUFFER];
int v[NMAX], w[NMAX], idx[NMAX], len[NMAX], aib[NMAX], f[NMAX];
void update(int from, int given, int N)
{
for(; from <= N; from += (from & -from))
{
if(len[aib[from]] < len[given]) aib[from] = given;
}
}
int query(int from)
{
int maxIndex = 0;
for(; from; from -= (from & -from))
{
if(len[aib[from]] > len[maxIndex]) maxIndex = aib[from];
}
return maxIndex;
}
inline bool isDig(char x) {return x >= '0' && x <= '9';}
inline void Read(istream& in, int& x)
{
static int till = -1;
if(-1 == idxBuffer)
{
till = in.readsome(buffer, MAXBUFFER);
}
while(!isDig(buffer[idxBuffer]))
{
if(++idxBuffer == till)
{
till = in.readsome(buffer, MAXBUFFER);
}
}
for(x = 0; isDig(buffer[idxBuffer]); )
{
x = x * 10 + buffer[idxBuffer] - '0';
if(++idxBuffer == till)
{
till = in.readsome(buffer, MAXBUFFER);
}
}
}
inline void output(ostream& out, int x)
{
if(!x) return;
output(out, f[x]);
out << v[x] << ' ';
}
int main()
{
int N, i, maxIndex;
ifstream in("scmax.in");
ofstream out("scmax.out");
Read(in, N);
for(i = 1; i <= N; ++i)
{
Read(in, v[i]);
w[i] = v[i];
}
sort(w + 1, w + N + 1);
for(i = 1; i <= N; ++i)
{
idx[i] = lower_bound(w + 1, w + N + 1, v[i]) - w;
}
maxIndex = 0;
for(i = 1; i <= N; ++i)
{
f[i] = query(idx[i] - 1);
len[i] = 1 + len[f[i]];
if(len[maxIndex] < len[i]) maxIndex = i;
update(idx[i], i, N);
}
out << len[maxIndex] << '\n';
output(out, maxIndex);
return EXIT_SUCCESS;
}