Cod sursa(job #913292)

Utilizator PatrikStepan Patrik Patrik Data 13 martie 2013 11:23:06
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
    #include<cstdio>
    using namespace std;
    #define MAX 100001
    int n , v[MAX] , A[4*MAX] , best[MAX] , pre[MAX] , poz , maxim , maxx ;

    void citire();
    void build(int n , int l , int r);
    void solve();
    void tipar();
    void query(int n , int l , int r , int x);
    void path(int i);

    int main()
    {
        citire();
        solve();
        tipar();
        return 0;
    }

    void citire()
    {
        freopen("scmax.in" , "r" , stdin );
        scanf("%d" , &n );
        for(int i = 1 ; i <= n ; ++i )
            scanf("%d" , &v[i]);
    }

    void build(int n , int l , int r )
    {
        if(l == r){A[n] = l;return;}
            int m = (l+r)/2;
            build(2*n,l,m);
            build(2*n+1,m+1,r);
        if(v[A[2*n]] <= v[A[2*n+1]])A[n] = A[2*n];
        else A[n] = A[2*n+1];
    }

    void solve()
    {
        build(1,1,n);
        best[1] = 1;
        for( int i = 2 ; i <= n ; ++i )
        {
            maxx = poz = 0;
            query(1,1,n,i-1);
            best[i] = best[poz]+1;
            pre[i] = poz;
        }
        for(int i = 1 ; i <= n  ; ++i )
            if(maxim < best[i])maxim = best[i],poz = i;
    }

    void query(int p , int l , int r , int x)
    {
        if(x < l || v[A[p]] >= v[x+1])return;
         if(l == r)
        {
            if(maxx < best[A[p]])
            {
                maxx = best[A[p]];
                poz = A[p];
            }
            return ;
        }
        int m = (l+r)/2;
        query(2*p,l,m,x);
        query(2*p+1,m+1,r,x);
    }

   void tipar()
   {
       freopen("scmax.out" , "w" , stdout );
       printf("%d\n" , maxim);
       path(poz);
   }

   void path(int poz)
   {
       if(!pre[poz])printf("%d " , v[poz]);
       else
       {
           path(pre[poz]);
           printf("%d " , v[poz]);
       }
   }