Pagini recente » Cod sursa (job #1272853) | Cod sursa (job #1530566) | Cod sursa (job #1858253) | Cod sursa (job #761448) | Cod sursa (job #2351229)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int N=100005;
int n,v[N],l[N],scl[N],log2[N],lmax,r[N];
int binsc(int x)
{
int y,p=0;
for(int bit=log2[lmax];bit>=0;bit--)
{
y=(1<<bit);
if(v[l[p+y]]<v[x])
p=p+y;
}
return p;
}
int main()
{
int poz;
in>>n;
v[0]=2000000005;
for(int i=1;i<=n;i++)
in>>v[i];
for(int i=2;i<=N;i++)
log2[i]=1+log2[i/2];
lmax=0;
for(int i=1;i<=n;i++)
{
poz=binsc(i);
if(v[i]<v[l[poz+1]])
{
l[poz+1]=i;
r[i]=poz+1;
lmax=max(lmax,poz+1);
}
}
out<<lmax<<'\n';
int i=l[lmax];
int lmx=lmax,last=v[0];
vector<int>sol;
for(i;i>0;i--)
{
if(r[i]==lmx && last>v[i])
{
sol.push_back(v[i]);
last=v[i];
lmx--;
}
}
for(i=sol.size()-1;i>=0;i--)
out<<sol[i]<<' ';
return 0;
}