Cod sursa(job #2613540)
Utilizator | Nae Teodora Ioana teodora019 | Data | 9 mai 2020 22:06:37 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 10 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.97 kb |
#include <fstream>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int v[100001],l[100001],d[100001],rez[100001];
int main ()
{
int k=0, n, i, st, dr, m, ck, poz;
cin>>n;
for (i=1; i<=n; i++)
{
cin>>v[i];
if (v[i]>l[k])
{
k++;
l[k]=v[i];
d[i]=k;
}
else
{
st=1;
dr=k;
while (st<=dr)
{
m=(st+dr)/2;
if (l[k]>=v[i])
{
poz=k;
dr=m-1;
}
else
st=m+1;
}
l[poz]=v[i];
d[i]=poz;
}
}
cout<<k<<'\n';
ck=k;
for (i=n; i>=1; i--)
if (d[i]==ck)
{
rez[ck]=v[i];
ck--;
}
for (i=1; i<=k; i++)
cout<<rez[i]<<" ";
return 0;
}