Cod sursa(job #1412613)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 1 aprilie 2015 13:14:36
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.87 kb
#include<cstdio>
#include<iostream>

int arb[200100];
int parb[200100];
int vect[100001];
int len[100001];
int from[100001];
int maxim,position,keep,maximum;
FILE *fin,*fout;

void show(int pos)
{
    if(from[pos]==pos)
    {
        fprintf(fout,"%d ",vect[pos]);
        return;
    }
    else
    {
        show(from[pos]);
    }
    fprintf(fout,"%d ",vect[pos]);
}

int ma(int a,int b)
{
    if(a>b)
    {
        return a;
    }
    return b;
}

int build(int st,int dr,int nod)
{
    if(st==dr)
    {
        arb[nod]=vect[st];
        parb[nod]=st;
        //fprintf(fout,"%d %d\n",parb[nod],nod);
    }
    else
    {
        int m=(st+dr)/2;
        build(st,m,nod*2);
        build(m+1,dr,nod*2+1);
        arb[nod]=ma(arb[nod*2],arb[nod*2+1]);
        if(arb[nod*2]>arb[nod*2+1])
        {
            parb[nod]=parb[nod*2];
        }
        else
        {
            parb[nod]=parb[nod*2+1];
        }
        //fprintf(fout,"%d %d\n",parb[nod],nod);
    }
}

void tofind(int st,int dr,int nod,int p1,int p2,int p)
{
    //std::cout<<st<<" "<<dr<<" "<<nod<<" "<<p1<<" "<<p2<<" "<<p<<'\n';
    if(st<=p1&&dr>=p2)
    {
        if(arb[nod]>=vect[p])
        {
            if(st==dr)
            {
                return;
            }
            else
            {
                int m=(p1+p2)/2;
                tofind(st,dr,nod*2+1,m+1,p2,p);
                tofind(st,dr,nod*2,p1,m,p);
            }
        }
        else
        {
            if(len[parb[nod]]>maxim)
            {
                maxim=len[parb[nod]];
                position=parb[nod];
            }
        }
    }
    else
    {
        int m=(p1+p2)/2;
        if(dr<=m)
        {
            //std::cout<<st<<" "<<dr<<" "<<nod<<" "<<p1<<" "<<p2<<" *** "<<p<<'\n';
            tofind(st,dr,nod*2,p1,m,p);
        }
        else if(st>m)
        {
            tofind(st,dr,nod*2+1,m+1,p2,p);
        }
        else
        {
            tofind(st,dr,nod*2,p1,m,p);
            tofind(st,dr,nod*2+1,m+1,p2,p);
        }
    }
}

int main()
{
    fin=fopen("scmax.in","r");
    fout=fopen("scmax.out","w");

    int n;
    fscanf(fin,"%d",&n);
    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%d",&vect[i]);
    }

    build(1,n,1);
    //fprintf(fout,"\n");
    len[1]=1;
    from[1]=1;
    keep=1;
    maximum=1;
    for(int i=2;i<=n;i++)
    {
        maxim=0;
        tofind(1,i-1,1,1,n,i);
        if(maxim==0)
        {
            len[i]=1;
            from[i]=i;
        }
        else
        {
            len[i]=len[position]+1;
            from[i]=position;
        }
       //fprintf(fout,"%d %d %d\n\n",maxim,position,len[i]);
        if(len[i]>maximum)
        {
            maximum=len[i];
            keep=i;
        }
    }
    fprintf(fout,"%d\n",len[keep]);
    show(keep);
}