Cod sursa(job #2203412)
Utilizator | Data | 12 mai 2018 11:18:34 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 55 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.96 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, st, dr, nr=1, mij, pozitie;
int v[100001], sol[100001], poz[100001];
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
fin>>v[i];
sol[1]=v[1];
poz[1]=1;
for(int i=2; i<=n; i++)
{
if(v[i]>sol[nr])
{
nr++;
sol[nr]=v[i];
poz[i]=nr;
}
if(v[i]<sol[nr])
{
st=1;
dr=nr;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[i]>=sol[mij])
st=mij+1;
else
{
dr=mij-1;
pozitie=mij;
}
}
sol[pozitie]=v[i];
poz[i]=pozitie;
}
}
fout<<nr<<"\n";
for(int i=1; i<=nr; i++)
fout<<sol[i]<<" ";
return 0;
}