uva 481 - What Goes Up

/*

Problem link

This is a must-use O(n.log(k)) LIS. It is the same as the uva 231 problem, a little bit troublesome when trace back for the result.

Go to this link to see more detail on O(n.log(k)) algorithm

for LIS at uva 231: http://nminhtu94.blogspot.com/2012/11/uva-231-testing-catcher-version-2.html

*/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 100000;
//----------------------------
class element { public: int value; int index;};
//----------------------------
element a[maxn],lis[maxn];
int trace[maxn],ans[maxn];
int n;
//----------------------------
int BSearch(int i, int j, int x) {
 int l,r,m;
 l = i; r = j; 
 if (r<l) return(-1);
 do
 {
  m = (l+r)/2;
  if (lis[m].value>=x) r = m;
  else l = m;
 } while (r-l>1);
 if (lis[l].value>=x) return(l);
 else if (lis[r].value>=x) return(r);
 else return(-1);
}
//----------------------------
int solve() {
 int result = 0;
 for (int i=1; i<=n; i++)
 {
  int pos = BSearch(1,result,a[i].value);
  if (pos!=-1) 
  {
   lis[pos] = a[i];
   if (pos==1) trace[i] = -1;
   else trace[i] = lis[pos-1].index;
  }
  else 
  {
   lis[++result] = a[i];
   if (result==1) trace[i] = -1;
   else trace[i] = lis[result-1].index;
  }
 }
 int cnt = 0, x = lis[result].index;
 while (trace[x]!=-1)
 {
  ans[++cnt] = a[x].value;
  x = trace[x];
 }
 ans[++cnt] = a[x].value;
 return(result);
}
//----------------------------
int main() {
 n = 0;
 int result;
 while (!cin.eof()) 
 {
  cin >> a[++n].value;
  a[n].index = n;
 }
 result = solve();
 cout << result << endl << "-" << endl;
 for (int i=result; i>=1; i--) cout << ans[i] << endl;
 return 0;
}
//----------------------------