Cod sursa(job #2807685)

Utilizator victorzarzuZarzu Victor victorzarzu Data 24 noiembrie 2021 09:16:16
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f 

using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n, d[100001], t[100001], v[100001];

void reconstruct(int x)
{
  if(t[x])
    reconstruct(t[x]); 
  g<<v[x]<<" ";    
}

void solve()
{
  d[1] = 1;
  int len = 1;
  int left, right, mid;

  for(int i = 2;i <= n;++i)
  {
    left = 1, right = len;
    while(left <= right)
    {
      mid = (left + right) >> 1;
      if(v[d[mid]] >= v[i])
        right = mid - 1;
      else
        left = mid + 1;
    }

    if(left > len)
    {
      ++len;
      d[len] = i;
      t[i] = d[len - 1];
    }
    else
    {
      d[left] = i;
      t[i] = d[left - 1];
    }
  }
  
  g<<len<<'\n';
  reconstruct(d[len]);
}

void read()
{
  f>>n;
  for(int i = 1;i <= n;++i)
    f>>v[i];
  solve();
} 

int main()
{
  read();
  return 0;
}