Cod sursa(job #2351229)

Utilizator DovlecelBostan Andrei Dovlecel Data 22 februarie 2019 09:02:53
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int N=100005;
int n,v[N],l[N],scl[N],log2[N],lmax,r[N];

int binsc(int x)
{
    int y,p=0;
    for(int bit=log2[lmax];bit>=0;bit--)
    {
        y=(1<<bit);
        if(v[l[p+y]]<v[x])
            p=p+y;
    }
    return p;
}

int main()
{
    int poz;
    in>>n;
    v[0]=2000000005;
    for(int i=1;i<=n;i++)
        in>>v[i];
    for(int i=2;i<=N;i++)
        log2[i]=1+log2[i/2];
    lmax=0;
    for(int i=1;i<=n;i++)
    {
        poz=binsc(i);
        if(v[i]<v[l[poz+1]])
        {
            l[poz+1]=i;
            r[i]=poz+1;
            lmax=max(lmax,poz+1);
        }
    }
    out<<lmax<<'\n';
    int i=l[lmax];
    int lmx=lmax,last=v[0];
    vector<int>sol;
    for(i;i>0;i--)
    {
        if(r[i]==lmx && last>v[i])
        {
            sol.push_back(v[i]);
            last=v[i];
            lmx--;
        }
    }
    for(i=sol.size()-1;i>=0;i--)
        out<<sol[i]<<' ';
    return 0;
}