Cod sursa(job #3174423)
| Utilizator | Data | 24 noiembrie 2023 19:12:30 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 55 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.08 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, a[100005], l[100005], poz[100005], lg=1, maax=1;
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>a[i];
}
l[lg++]=a[1];
poz[1]=1;
for(int i=2; i<=n; i++)
{
if(a[i]>l[lg-1])
{
poz[i]=maax++;
l[lg++]=a[i];
}
else
{
int st=1, dr=lg;
while(st<=dr)
{
int mij=(st+dr)/2;
if(l[mij]>a[i] && l[mij-1]<=a[i])
{
l[mij]=a[i];
poz[i]=poz[mij];
break;
}
if(l[mij]<a[i])
{
st=mij+1;
}
else
{
dr=mij-1;
}
}
}
}
fout<<maax<<"\n";
for(int i=1; i<=lg-1; i++)
{
fout<<l[i]<<" ";
}
return 0;
}
