Cod sursa(job #3197978)

Utilizator cacamaca12aasdga cacamaca12 Data 27 ianuarie 2024 20:11:37
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <stack>
#define dim 100003
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");

stack<int>Q;
int v[dim],q[dim],p[dim];
int lg,n;

void insert(int val,int indice){
    if(q[lg]==val) return;
    if(q[lg]<val) q[++lg]=val,p[indice]=lg;
    else{
        int st=1,dr=lg,m,poz;
        while(st<=dr){
            int m=(st+dr)/2;
            if(q[m]>val) poz=m,dr=m-1;
            else st=m+1;
            if(q[m]==val) return;
        }
        q[poz]=val;
        p[indice]=poz;
    }
}

void reconst(){
    for(int i=n;i>=1;--i){
        if(p[i]==lg) --lg,Q.push(v[i]);
        if(!lg) break;
    }
    
    while(!Q.empty()){
        cout<<Q.top()<<" ";
        Q.pop();
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>v[i];
        insert(v[i],i);
    }
    cout<<lg<<'\n';
    reconst();
    
    return 0;
}