UVa 497 - Strategic Defense Initiative

// Accepted

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>

#define high 10110

using namespace std;

typedef long long LL;

const LL inf = 2147483648;

LL seq[high], I[high] , L[high] , lisseq[high];

void LIS(int n)
{
    int i , j;
    LL len=0;

    I[0] = -inf;

    for(i=1; i<=n; i++)
    {
        I[i] = inf;
    }

    for(i=0; i<n; i++)
    {
        L[i] = 1;
    }

    for(i=0; i<n; i++)
    {
        int lo=0, hi=len, mid;

        while(lo <= hi)
        {
            mid = (lo + hi) / 2;

            if(I[mid] < seq[i])
            {
                lo = mid + 1;
            }

            else
            {
                hi = mid - 1 ;
            }
        }

        I[lo] = seq[i];
        L[i] = lo;

        if(len < lo)
        {
            len = lo;
        }
    }

    cout << "Max hits: " << len <<"\n" ;

    i=0;

    for(j=1; j<n; j++)
    {
        if(L[i] < L[j])
        {
            i = j;
        }
    }

    int top = L[i];

    top--;

    lisseq[top] = seq[i];

    for(j=i-1; j>=0; j--)
    {
        if(seq[i] > seq[j] and L[j] == L[i] - 1)
        {
            i = j;

            top--;

            lisseq[top] = seq[i];
        }
    }

    for(i=0; i<len; i++)
    {
        cout << lisseq[i] << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(0);

    int t;
    string s;
    LL x;
    cin >> t;
    cin.ignore();
    cin.ignore();

    while(t--)
    {
        int slen=0;

        while(getline(cin,s,'\n'))
        {
            if(s.length() == 0) break;

            stringstream ss(s);
            ss >> x;
            seq[slen++] = x;
        }

        //for(int i=0; i<slen; i++) cout << seq[i] << " ";

        //cin.ignore();

        LIS(slen);

        if(t > 0)
        {
            cout << "\n";
        }
    }

    return 0;
}