Longest Increasing Subsequence (LIS) O(nlogk)

#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
#define siz 1000005
#define INF INT_MAX
int L[siz],I[siz],a[siz],LisSequence[siz];
char as[siz];
int n;
vector <int> vec;

int LIS(){
    int i;
    I[0]=-INF;
    for(i=1;i<=n;i++)
        I[i]=INF;

    int LisLength=0;

    for(i=0;i<n;i++){
        int low,high,mid;
        low=0;
        high=LisLength;

        while(low<=high){
            mid=(low+high)/2;
            if(I[mid]<a[i]) low=mid+1;
            else high=mid-1;
        }
        I[low]=a[i];
        if(LisLength<low) LisLength=low;
        L[i]=low;
    }
    return LisLength;
}

void LISpathPrint(int lis){
    for(int i=n;i>=0;i--){
        if(lis==0) break;
        if(lis==L[i]){
            vec.push_back(a[i]);
            lis--;
        }
    }
    for(int i=vec.size()-1;i>=0;i--)
        printf("%d\n",vec[i]);

    vec.clear();
}
int main()
{
    int lis,x,k=1,lastVal,N;
    //freopen("input.txt","r",stdin);
    scanf("%d",&N);
    getchar();
    getchar();
    for(int t=0;t<N;t++){
        if(t!=0) printf("\n");
        n=0;
        while (gets(as)&&strlen (as) ) {
            a[n++]=atoi(as);
        }
        lis=LIS();
        printf("Max hits: %d\n",lis);
        LISpathPrint(lis);
    }

    return 0;
}