Pagini recente » Cod sursa (job #1782965) | Cod sursa (job #1223095) | Cod sursa (job #1373961) | Cod sursa (job #2595311) | Cod sursa (job #1163287)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int lsb(int nr)
{
return ((nr)&(-nr));
}
int aib[100005];
void update(int where,int val)
{
int i;
for (i=where;i<100003;i+=lsb(i))
aib[i]=max(aib[i],val);
}
int query(int where)
{
int i,mx;
mx=0;
for (i=where;i>0;i-=lsb(i))
mx=max(mx,aib[i]);
return mx;
}
int i,n,nr,last,mx,l,mxl,vl[100005],sz,iv;
vector <pair<int,int> > v;
vector <int> rv,r,v2;
char s[2000005];
int main(void)
{
FILE * f;
f=fopen("scmax.in","r");
ofstream g("scmax.out");
fscanf(f,"%d",&n);
fgets(s,20,f);
fgets(s,2000003,f);
sz=strlen(s);
iv=0;
for (i=0;i<sz;i++)
{
if ((s[i]>='0')&&(s[i]<='9'))
nr=nr*10+s[i]-'0';
else
{
v.push_back(make_pair(nr,iv));
v2.push_back(nr);
rv.push_back(nr);
nr=0;
iv++;
}
}
sort(v.begin(),v.end());
nr=1;
v2[v[0].second]=nr;
for (i=1;i<v.size();i++)
{
if (v[i].first!=v[i-1].first)
nr++;
v2[v[i].second]=nr;
}
for (i=0;i<v.size();i++)
{
nr=v2[i];
mx=query(nr-1);
l=mx+1;
vl[i]=l;
if (l>mxl)
mxl=l;
update(nr,l);
}
i=n;
while (vl[i]!=mxl)
i--;
last=i;
r.push_back(rv[last]);
for (;i>0;i--)
{
if ((vl[i]==vl[last]-1)&&(v2[i]<v2[last]))
{
r.push_back(rv[i]);
last=i;
}
}
if (v2[i]<v2[last])
r.push_back(rv[i]);
g<<r.size()<<'\n';
for (i=r.size()-1;i>=0;i--)
g<<r[i]<<' ';
g<<'\n';
g.close();
return 0;
}