Cod sursa(job #2470342)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 9 octombrie 2019 01:11:05
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;
#define lsb(x) (x&(-x))

FILE *fin=freopen("scmax.in","r",stdin);
FILE *fout=freopen("scmax.out","w",stdout);


static const int NMAX = 1e5+5;

int aib[NMAX];
int ind[NMAX];
int v[NMAX];
int unique_id[NMAX];
int lst[NMAX];
int previous[NMAX];
int best[NMAX];

int n;

int query(int position)
{
    int  mx = 0;
    for(int i = position; i>= 1; i-=lsb(i))
    {
        //mx = max(mx, aib[i]);
        if(best[aib[i]] > best[mx])
        {
            mx = aib[i];
        }
    }
    return mx;
}

void update(int position, int value,int nn)
{
    for(int i = position;i<=nn; i+=lsb(i))
    {
        //aib[i] = max(aib[i],value);
        if(best[value] > best[aib[i]])
        {
            aib[i] = value;
        }
    }
}

int main()
{
    
    scanf("%d",&n);
    for(int i = 1; i<=n; ++i)
    {
        scanf("%d",&v[i]);
        lst[i] = v[i];
        unique_id[i] = v[i];
    }

    int k =1;
    sort(lst+1,lst+n+1);
    for (int i = 2; i <= n; ++i)
		if (lst[i] != lst[k])
			lst[++k] = lst[i];

    for(int i = 1; i<=n; ++i)
    {
        unique_id[i] = lower_bound(lst+1,lst+k+1,unique_id[i])-lst;
    }
    int maxi = 1;
    int indice_maxi = 1;
    for(int i =1; i<=n; ++i)
    {
        // Gasesc suma cea mai mare pt elemente mai mici decat elem curent
        int number_before = query(unique_id[i]-1);

        previous[unique_id[i]] = number_before;
        best[unique_id[i]] = best[number_before]+1;
        if(best[unique_id[i]] > maxi)
        {
            maxi = best[unique_id[i]];
            indice_maxi = unique_id[i];
        }

        update(unique_id[i],unique_id[i],k);
    }
    
    vector<int> sol;
    while(indice_maxi)
    {
        sol.push_back(lst[indice_maxi]);
        indice_maxi =previous[indice_maxi];
    }

    //fout << maxi << '\n';
    printf("%d\n",maxi);
    for(int i = (int) sol.size()-1; i>= 0; i--)
    {
        //fout << sol[i] << " ";
        printf("%d ",sol[i]);
    }
    return 0;
}