Cod sursa(job #1208887)

Utilizator acomAndrei Comaneci acom Data 16 iulie 2014 18:40:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define NMAX 100005
vector <int> v;
vector <int>::reverse_iterator it;
int n,m,nr,num,a[NMAX],b[NMAX],A[NMAX],B[NMAX],L[NMAX],V[NMAX];
inline void update(int p, int x)
{
    for (;p<=n;p+=(p&-p))
        V[p]=max(x,V[p]);
}
inline int maxim(int p)
{
    int Max=0;
    for (;p>0;p-=(p&-p))
        Max=max(Max,V[p]);
    return Max;
}
inline int cauta(int x)
{
    int st,dr,mij;
    st=1, dr=n;
    while (st<=dr)
    {
        mij=st+((dr-st)>>1);
        if (x==b[mij]) return B[mij];
        else
        {
            if (x<b[mij]) dr=mij-1;
            else st=mij+1;
        }
    }
    return 0;
}
int main()
{
    int i;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    m=0;
    for (i=1;i<=n;++i)
        if (b[i]!=b[i-1])
            B[i]=++m;
        else
            B[i]=m;
    for (i=1;i<=n;++i)
    {
        A[i]=cauta(a[i]);
        nr=maxim(A[i]-1);
        update(A[i],++nr);
        L[i]=nr;
        num=max(num,nr);
    }
    printf("%d\n",num);
    for (i=n;i>0 && num;--i)
        if (L[i]==num)
        {
            v.push_back(a[i]);
            --num;
        }
    for (it=v.rbegin();it!=v.rend();++it)
        printf("%d ",*it);
    printf("\n");
    return 0;
}