Cod sursa(job #2718276)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 8 martie 2021 17:08:31
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda no-time-to-rest Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,v[100005],best[100005],l[100005],sir[100005],nr,tr;

int caut_bin(int x)
{
 int st=1,dr=nr,mid,rasp=nr+1;

 while( st<=dr )
 {
  mid=(st+dr)/2;
  if( v[l[mid]]>=x ) rasp=mid,dr=mid-1;
  else st=mid+1;
 }

 return rasp;
}

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

 for(int i=1;i<=n;i++)
 {
  int poz = caut_bin(v[i]);

  l[poz]=i;
  best[i]=poz;
  if(poz>nr) nr++;
 }

 g<<nr<<'\n';
 int maxim=2000000005;

 for(int i=n;i>=1&&nr>=1;i--)
 {
  if( best[i]==nr&&v[i]<maxim ) sir[++tr]=v[i],maxim=v[i],nr--;
 }
 for(int i=tr;i>=1;i--) g<<sir[i]<<' ';
}