Cod sursa(job #2676315)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 23 noiembrie 2020 22:35:21
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
const int NMAX=100005;
int n,x,pos,length=1,maxx,v[NMAX],L[NMAX],best[NMAX],p[NMAX];
void write(int i)
{
    if(p[i]>0)
        write(p[i]);
    g<<v[i]<<" ";
}
int binarysearch(int x)
{
    int left=0,right=length;
    while(left<=right)
    {
        int middle=(left+right)/2;
        if(v[L[middle]]<x && v[L[middle+1]]>=x)
            return middle;
        else if(v[L[middle+1]]<x)
            left=middle+1;
        else
            right=middle-1;
    }
    return length;
}
int main()
{
    best[1]=L[1]=1;
    f>>n;
    for(int i=1; i<=n; i++)
        f>>v[i];
    for(int i=2; i<=n; i++)
    {
        pos=binarysearch(v[i]);
        p[i]=L[pos];
        best[i]=pos+1;
        L[pos+1]=i;
        if(length<pos+1)
            length=pos+1;
    }
    for(int i=1; i<=n; i++)
        if(maxx<best[i])
        {
            maxx=best[i];
            pos=i;
        }
    g<<maxx<<"\n";
    write(pos);
    return 0;
}