Cod sursa(job #2432987)

Utilizator KataIsache Catalina Kata Data 25 iunie 2019 17:04:58
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
long long int v[100002],a[100002];
int lg[100002],prev[100002];
int main()
{
 int n,i,lgmax=0,j,st,dr,mijloc;
 fin>>n;
 for(i=1;i<=n;i++) fin>>v[i];
 //for(i=0;i<=10001;i++) lg[i]=-1;
 for(i=1;i<=n;i++)
     {
       if(v[i]>v[lg[lgmax]]) {lg[++lgmax]=i;
                              prev[i]=lg[lgmax-1];
                             }
       else {
             st=0;
             dr=lgmax+1;
            while (dr-st>1)
                  {mijloc=(st+dr)/2;
                   if (v[lg[mijloc]]<v[i])
                       st=mijloc;
                   else dr=mijloc;
                   }
            lg[dr]=i;
            prev[i]=lg[dr-1];
                                    }
     }
 fout<<lgmax<<'\n';
 i=lg[lgmax];j=lgmax;
 while(prev[i])
 {
     a[j--]=v[i];
     i=prev[i];
 }
 if(a[1]==0)a[1]=v[i];
 for(i=1;i<=lgmax;i++) fout<<a[i]<<" ";

 return 0;
}