Pagini recente » Cod sursa (job #660275) | Cod sursa (job #2951677) | Cod sursa (job #2152594) | Cod sursa (job #2438736) | Cod sursa (job #617389)
Cod sursa(job #617389)
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define INFILE "scmax.in"
#define OUTFILE "scmax.out"
#define AMAX 2000000000
#define NMAX 100000
struct nod{
nod* l;
nod* r;
int best;
nod() : l(NULL), r(NULL), best(0) {}
};
nod* t;
int N;
int a[NMAX], b[NMAX];
int add(nod* n, int lv, int rv, int val, int best)
{
if( lv==rv )
{
n->best = best + 1;
return n->best;
}
int mid = (lv+rv) / 2;
if( n->l==NULL ) n->l = new nod();
if( n->r==NULL ) n->r = new nod();
if( mid<val )
n->best = max(add( n->r, mid+1, rv, val, max(best,n->l->best)), n->best);
else
n->best = max(add(n->l, lv, mid, val, best), n->best);
return n->best;
}
void printarray(int val, int i)
{
if( val && b[i]==val )
{
printarray(val-1, i-1);
printf("%d", a[i]);
if( val<t->best ) printf(" ");
}
else if( val )
printarray(val, i-1);
}
int main()
{
freopen(INFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
t = new nod();
scanf("%d", &N);
for(int i=0; i<N; i++)
{
scanf("%d", &a[i]);
b[i] = add(t, 0, AMAX, a[i], 0);
}
printf("%d\n", t->best);
printarray(t->best, N-1);
return 0;
}