Cod sursa(job #2450343)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 22 august 2019 19:50:31
Problema Subsir crescator maximal Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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];
vector <int> V;

int bSearch(int val)
{
    int st = 0, dr = V.size() - 1;
    while (dr - st > 1)
    {
        int mij = (st + dr) / 2;
        if (a[V[mij]] <= val)
            st = mij;
        else dr = mij;
    }
    return dr;
}


void Afis(int val)
{
    if (T[val] != -1)
        Afis(T[val]);
    fout << a[val] << " ";
}

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

    memset(T, -1, N);
    V.push_back(1);
    for (int i = 2; i <= n; i++)
    {
        if (a[i] > a[V.back()])
        {
            T[i] = V.back();
            V.push_back(i);
        }
        else if (a[i] < a[V[0]])
            V[0] = i;
        else
        {
            int index = bSearch(a[i]);
            V[index] = i;
            T[i] = V[index - 1];
        }
    }

    fout << V.size() << "\n";
    Afis(V.back());

    return 0;
}