Cod sursa(job #1698014)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 3 mai 2016 14:53:45
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
#define Nmax 100007
int N,V[Nmax],x,y,T[Nmax],L[Nmax],Arb[4*Nmax],poz,val,R,maxi=0,pmax;
void add(int nod,int st,int dr)
{
    if(st==dr){
        Arb[nod]=y;
        return;
    }
    int mij=(st+dr)/2;
    if(x<=mij) add(2*nod,st,mij);
    else add(2*nod+1,mij+1,dr);
    if(L[Arb[2*nod]]>L[Arb[2*nod+1]]) Arb[nod]=Arb[2*nod];
    else Arb[nod]=Arb[2*nod+1];
}
void caut(int nod,int st,int dr)
{
    if(st>=x&&dr<=y&&V[Arb[nod]]<R){
        if(L[Arb[nod]]>val) val=L[Arb[nod]], poz=Arb[nod];
        return;
    }
    int mij=(st+dr)/2;
    if(x<=mij) caut(2*nod,st,mij);
    if(y>mij)  caut(2*nod+1,mij+1,dr);
}
void rafis(int x)
{
    if(T[x]) rafis(T[x]);
    g<<V[x]<<" ";
}
int main()
{
    f>>N; V[0]=0;
    for(int i=1;i<=N;++i){
        f>>V[i];
        R=V[i];
        if(i==1){
          L[1]=1;
          T[1]=0;
          x=i; y=i;
          add(1,1,N);
          continue;
        }
        poz=0; val=0;
        x=1; y=i-1;
        caut(1,1,N);
        if(poz==0) L[i]=1, T[i]=0;
        else L[i]=L[poz]+1, T[i]=poz;
        x=i; y=i;
        add(1,1,N);
        if(L[i]>maxi) maxi=L[i], pmax=i;
    }
    g<<maxi<<'\n';
    rafis(pmax);
    g<<'\n';
    return 0;
}