Cod sursa(job #721796)

Utilizator test0Victor test0 Data 24 martie 2012 10:24:45
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <vector>
using namespace std;
vector<int>v;
int bst[100005],a[100005],c[100005],n,k;

int insert(int st,int dr,int x){
    if(st==dr){
        c[st]=x;
        if(st==k+1)k++;
        return st; } else {
    int md=(st+dr)/2;
    if(c[md]>=x)insert(st,md,x); else insert(md+1,dr,x); }
}

int main(){
    int x;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
        scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        bst[i]=insert(1,k+1,a[i]);}
    printf("%d\n",k);
    for(int i=n;i>0;i--)
    if(bst[i]==k){v.push_back(a[i]); k--;}
    for(;v.size()>0;){
        printf("%d ",v.back());
        v.pop_back();}
}