Cod sursa(job #2572462)
| Utilizator | Data | 5 martie 2020 12:53:53 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.72 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int a[100002],b[100002],c[100002];
int main()
{
int n,i,r,pas,m=0;
in>>n;
for(i=0; i<n; i++)
{
in>>a[i];
r=0;
pas=1<<30;
while(pas)
{
if(r+pas<=m&&a[i]>a[b[r+pas]])
r+=pas;
pas>>=1;
}
b[++r]=i;
if(r!=1)
c[i]=b[r-1];
else
c[i]=-1;
m=max(m,r);
}
for(r=b[m],i=0; c[r]!=-1; r=c[r],i++)
b[i]=a[r];
b[i]=a[r];
out<<m<<"\n";
for(i=m-1; i>=0; i--)
out<<b[i]<<" ";
}
