Pagini recente » Cod sursa (job #2330546) | Cod sursa (job #253500) | Cod sursa (job #1809029) | Cod sursa (job #1321244) | Cod sursa (job #1143569)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int aib[100005],v[100005],k[100005];
int n,i,nr,q,mx,last,mxn;
vector <pair <int,int> > axv1;
vector <int> r,axv,axv2;
int lsb(int nr)
{
int ax=((nr)&(-nr));
return ax;
}
int query(int pos)
{
int mx=0;
for (int i=pos;i>0;i-=lsb(i))
mx=max(mx,aib[i]);
return mx;
}
void update(int val,int pos)
{
for (int i=pos;i<=mxn;i+=lsb(i))
aib[i]=max(aib[i],val);
}
int main(void)
{
FILE * f;
f=fopen("scmax.in","r");
ofstream g("scmax.out");
fscanf(f,"%d",&n);
for (i=1;i<=n;i++)
{
fscanf(f,"%d",&nr);
axv1.push_back(make_pair(nr,i-1));
axv.push_back(nr);
axv2.push_back(nr);
}
sort(axv1.begin(),axv1.end());
nr=1;
axv2[axv1[0].second]=nr;
//axv2.push_back(make_pair(axv1[0].second,nr));
for (i=1;i<axv1.size();i++)
{
for (;(i<axv1.size())&&(axv1[i-1].first==axv1[i].first);i++)
//axv2.push_back(make_pair(axv1[i].second,nr));
axv2[axv1[i].second]=nr;
nr++;
//axv2.push_back(make_pair(axv1[i].second,nr));
axv2[axv1[i].second]=nr;
}
mxn=nr;
//sort(axv2.begin(),axv2.end());
for (i=0;i<axv2.size();i++)
{
nr=axv2[i];
q=query(nr-1);
v[i]=nr;
k[i]=q+1;
if (q+1>mx)
mx=q+1;
update(q+1,nr);
}
last=2000000002;
//for (i=0;i<=n;i++)
// cout<<k[i]<<' ';
//cout<<'\n';
//for (i=0;i<=n;i++)
// cout<<v[i]<<' ';
for (i=n-1;i>=0;i--)
if ((k[i]==mx)&&(v[i]<last))
{
r.push_back(i);
mx--;
last=v[i];
}
g<<r.size()<<'\n';
for (i=r.size()-1;i>=0;i--)
g<<axv[r[i]]<<' ';
return 0;
}