Cod sursa(job #2450350)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 22 august 2019 20:27:47
Problema Subsir crescator maximal Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#define N 100005

using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int n, a[N], T[N], V[N], lgMax, ans[N];

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> a[i];
        T[i] = -1;
    }

    lgMax = 1;
    V[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] > a[V[lgMax]])
        {
            lgMax++;
            V[lgMax] = i;
            T[i] = V[lgMax - 1];
        }
        else if (a[i] < a[V[1]])
        {
            V[1] = i;
            T[i] = -1;
        }
        else
        {
            int st = 1, dr = lgMax, index;

            while (st <= dr)
            {
                int mij = (st + dr) / 2;
                if (a[V[mij]] >= a[i])
                {
                    index = mij;
                    dr = mij - 1;
                }
                else st = mij + 1;
            }

            V[index] = i;
            T[i] = V[index - 1];
        }
    }

    fout << lgMax << "\n";

    int val = V[lgMax], lg = lgMax;
    while (lg--)
    {
        ans[lg] = a[val];
        val = T[val];
    }

    for (int i = 1; i <= lgMax; i++)
        fout << ans[i] << " ";

    return 0;
}