Cod sursa(job #3370903)

Utilizator tudorbuhniaTudor Buhnia tudorbuhnia Data 27 octombrie 2026 19:04:18
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

int v[100005], vo[100005], best[100005];

int aint[8*100001];
int n,m;

void update(int nod,int left,int right,int i,int x)
{
    if(left==i && right==i)
    {
        aint[nod]=x;
        return;
    }
    int mij=(left+right)/2;
    if(i<=mij) update(nod<<1,left,mij,i,x);
    else update(nod<<1|1,mij+1,right,i,x);
    aint[nod]=max(aint[nod<<1],aint[nod<<1|1]);
}
int query(int nod,int left,int right,int a,int b)
{
    if(left>=a && right<=b) return aint[nod];
    int mij=(left+right)/2;
    int nodst=0,noddr=0;
    if(a<=mij) nodst=query(nod<<1,left,mij,a,b);
    if(b>mij) noddr=query(nod<<1|1,mij+1,right,a,b);
    return max(nodst,noddr);
}

int main()
{
    ifstream cin("scmax.in");
    ofstream cout("scmax.out");

    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> v[i];
        vo[i] = v[i];
    }

    sort(v+1, v+n+1);

    unordered_map<int, int> rank;
    rank[v[1]] = 1;

    int last = v[1];
    int li = 2;

    for (int i = 2; i <= n; i++)
    {
        if (v[i] != last)
        {
            last = v[i];
            rank[last] = li;
            li++;
        }
    }

    //for(int i=0;i<=n;i++)
    //    cout << v[i] << " ";

    int m = li - 1;

    //cout << rank[19] << endl;
    //cout << m << endl;

    for(int i=1;i<=m;i++)
        update(1, 1, m, i, 1);

    best[1] = 1;

    for(int i=2;i<=n;i++)
    {
        int g = rank[vo[i]];

        //cout << g << " ";

        if(g >= 2)
        {
            int x = query(1, 1, m, 1, g - 1);
            best[i] = x + 1;
            update(1, 1, m, g, x + 1);
        }
        else
        {
            best[i] = 1;
        }
    }

    cout << query(1, 1, m, 1, m) << endl;

    return 0;
}