Cod sursa(job #2470332)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 9 octombrie 2019 00:37:21
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

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

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



static const int NMAX = 1e5+5;

int aib[NMAX];
int v[NMAX];
int unique_id[NMAX];
int previous[NMAX];
int best[NMAX];
int a[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);
    map<int,int> unique;
    for(int i = 1; i<=n; ++i)
    {
        //fin >> v[i];
        scanf("%d",&v[i]);
        unique[v[i]] = 0;
    }
 
    int k = 0;
    for(auto it = unique.begin(); it!= unique.end(); it++)
    {
        k++;
        unique[it->first] = k;
        a[k] = it->first;
    }

    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[v[i]]-1);

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

        update(unique[v[i]],unique[v[i]],k);
    }
    
    vector<int> sol;
    while(indice_maxi)
    {
        sol.push_back(a[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;
}