Cod sursa(job #2647789)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 6 septembrie 2020 14:24:03
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <climits>

using namespace std;

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

const int NMAX = 100000;

int v[1 + NMAX];
int t[1 + NMAX];

int l[1 + NMAX];
int l_idx[1 + NMAX];

int cautare(int st, int dr, int val) // lower_bound
{
  int last = -1;

  while (st <= dr)
  {
    int mij = (st + dr) / 2;
    if (l[mij] < val)
    {
      st = mij + 1;
    }
    else
    {
      last = mij;
      dr = mij - 1;
    }
  }

  return last;
}

int afisare_sol(int idx)
{
  if (t[idx] != 0)
  {
    afisare_sol(t[idx]);
  }

  out << v[idx] << ' ';
}

int main()
{
  int n;
  int sol = 0;

  in >> n;

  for (int i = 1; i <= n; i++)
  {
    l[i] = INT_MAX;

    in >> v[i];

    int poz = cautare(1, i, v[i]);

    l[poz] = v[i];
    l_idx[poz] = i;
    t[i] = l_idx[poz - 1];

    if (sol < poz)
    {
      sol = poz;
    }
  }

  out << sol << '\n';

  afisare_sol(l_idx[sol]);

  return 0;
}