Cod sursa(job #721722)

Utilizator bacilaBacila Emilian bacila Data 24 martie 2012 00:20:16
Problema Secv Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
using namespace std;
int n,a[100005],v[100005],k,st,dr,i,e[100005],t[100005],in,sf;
int main ()
{ifstream f("secv.in");
 ofstream g("secv.out");
f>>n;
a[0]=-(INT_MAX);
for(i=1;i<=n;i++)
f>>v[i];
for(i=1;i<=n;i++)
if(v[i]>a[k])
{a[++k]=v[i]; e[k]=i; t[i]=e[k-1];}
else{
st=1; dr=k;
while(st<=dr)
if(a[(st+dr)/2]>v[i]&&a[(st+dr)/2-1]<v[i])
{a[(st+dr)/2]=v[i]; e[(st+dr)/2]=i; t[i]=e[(st+dr)/2-1]; break;}
else
if(a[(st+dr)/2]>v[i]&&a[(st+dr)/2-1]>v[i])
dr=(st+dr)/2-1;
else
if(a[(st+dr)/2]<v[i]&&a[(st+dr)/2-1]<v[i])
st=(st+dr)/2+1;
else
break;
}
sf=e[k];
k=t[e[k]];
while(t[k]){
k=t[k];}
in=k;
g<<sf-in+1<<'\n';
for(i=in;i<=sf;i++)
g<<v[i]<<" ";
 f.close(); g.close();
return 0;
}