Pagini recente » Cod sursa (job #944624) | Cod sursa (job #1614490) | Cod sursa (job #1166008) | Cod sursa (job #2919738) | Cod sursa (job #1698012)
#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(V[Arb[2*nod]]>V[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;
}