Cod sursa(job #2627109)

Utilizator eugen5092eugen barbulescu eugen5092 Data 9 iunie 2020 19:52:13
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;
#define sp 100005
ifstream ci("scmax.in");
ofstream cou("scmax.out");
int k;
int n,v[sp],lis[sp],poz[sp];
int afis[sp];

void citire()
{
    ci>>n;
    for(int i=1; i<=n; i++)
    {
        ci>>v[i];
    }

}

int cautare(int st,int dr,int x)
{
    int m,p;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(lis[m] < x)
            st = m + 1;
        else
        {
            p = m;
            dr = m - 1;
        }
    }
    return p;

}


void rez()
{
    lis[1]=v[1];
    poz[1]=k=1;
    int i,p;
    for(i=2; i<=n; i++)
    {
        if(v[i]>lis[k] )
        {
            k++;
            lis[k]=v[i];
            poz[i]=k;
        }
        else
        {
            p=cautare(1,k,v[i]);

            lis[p]=v[i];
            poz[i]=p;

        }
    }

    cou<<k<<"\n";

    for(int i = n; i && k; i--)
        if(poz[i] == k)
            afis[k--] = v[i];
    while(afis[++k])
        cou << afis[k] << " ";

}

int main()
{
    citire();
    rez();
    return 0;
}