Cod sursa(job #617389)

Utilizator desoComan Andrei deso Data 14 octombrie 2011 19:21:30
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#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;
}