UVA - 481 - What Goes Up

#include <vector>
#include <cstdio>

using namespace std;

void LIS(vector<int> &input, vector<int> &lis){
    vector<int> temp(input.size());
    lis.push_back(0);
    int s, e;
    for (size_t i = 1; i < input.size(); i++){
        if (input[lis.back()] < input[i]){
            temp[i] = lis.back();
            lis.push_back(i);
            continue;
        }
        s = 0;
        e = lis.size()-1;
        while (s < e){
            int m = (s + e) / 2;
            if (input[lis[m]] < input[i])
                s=m+1;
            else
                e=m;
        }
        if (input[i] < input[lis[s]]){
            if (s > 0)
                temp[i] = lis[s-1];
            lis[s] = i;
        }
    }
    for (s = lis.size(), e = lis.back(); s--; e = temp[e])
        temp[s] = e;
}


int main()
{
    int x;
    vector<int> seq;
    while(scanf("%d",&x)==1){
        if(x==22)
            break;
        seq.push_back(x);
    }
    vector<int> lis;
    LIS(seq, lis);
    printf("%d\n-\n", lis.size());
    for (unsigned int i = 0; i < lis.size(); i++)
        printf("%d\n", seq[lis[i]]);
    return 0;
}