Pagini recente » Cod sursa (job #47684) | Cod sursa (job #2600031) | Cod sursa (job #2265700) | Cod sursa (job #1651934) | Cod sursa (job #709476)
Cod sursa(job #709476)
#include<fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,nr,v[100001],val[100001],best[100001],par[100001],k,i,aux;
inline void caut_binar()
{int step;
for (step=1;step<nr;step<<=1);
for (aux=0;step;step>>=1)
if (aux+step<nr && val[aux+step]<= v[i])
aux += step;
}
int main()
{ fin >> n;
for (i=1;i<=n;++i)
fin >> v[i];
for (i=1;i<=n;++i)
{ if (v[i] > val[nr])
{ val[++nr] = v[i];
best[i] = nr;
par[nr] = i;
}
else
{ caut_binar();
if (val[aux] != v[i])
{ ++aux;
val[aux] = v[i];
par[aux] = i;
best[i] = aux;
}
else
best[i] = aux;
}
}
long long max1 = 0;
max1 = 1LL<<40;
fout << nr << '\n';
k = nr;
int rasp[100001],ar=nr;
for (i=n;i>=1;--i)
if (best[i] == k && max1 > v[i])
{ rasp[ar] = v[i];
--ar;
--k;
max1 = v[i];
}
for (i=1;i<=nr;++i)
fout << rasp[i] << " ";
return 0;
}