Cod sursa(job #1866165)

Utilizator victoreVictor Popa victore Data 2 februarie 2017 18:20:51
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<cstdio>

using namespace std;
const int nmax=100005;
int q[nmax],p[nmax],sol[nmax],v[nmax],n,l=0,lmax=0;
int cautbin(int x)
{
    int st,dr,med;
    st=1;
    dr=l;
    while(st<=dr)
    {
        med=(st+dr)/2;
        if(q[med]<x)
            st=med+1;
        else
            dr=med-1;
    }
    if(q[st-1]==x&&st>l)
        return st-1;
    return st;
}
void aplica(int x,int a)
{
    int i;
    if(!l)
    {
        q[++l]=x;
        p[l]=1;
    }
    else if(l==1)
    {
        if(q[1]>x)
            {
                q[1]=x;
                p[a]=1;
            }
        else if(q[1]<=x)
        {
            q[++l]=x;
            p[a]=2;
        }
    }
    else
    {
        i=cautbin(x);
        if(i>l)
            l=i;
        q[i]=x;
        p[a]=i;
    }
    return;
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);
            aplica(v[i],i);
        }
    printf("%d\n",l);
    lmax=l;
    for(i=n;i>=0;i--)
    {
        if(p[i]==lmax)
        {
            sol[lmax]=v[i];
            lmax--;
        }
    }
    for(i=1;i<=l;i++)
        printf("%d ",sol[i]);
    
}