Cod sursa(job #2468376)

Utilizator raduzxstefanescu radu raduzx Data 5 octombrie 2019 14:53:37
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
#define nmax 100005
int n;
int vec[nmax],father[nmax],lung=0,poz_prec[nmax],new_vec[nmax],poz_act[nmax];
int caut_bin(int x){
    int mid,lo=1,hi=lung;
    while(lo<hi){
        mid=(lo+hi)/2;
        if(new_vec[mid]>=x and new_vec[mid-1]<x){
            return mid;
        }
        if(new_vec[mid]>x){
            hi=mid-1;
        }
        else{
            lo=mid+1;
        }
    }
    return lo;
}


void afisare_rec(int poz){
    if(poz!=0){
        afisare_rec(father[poz]);
        g<<vec[poz]<<" ";
    }
}
int main()
{
    int poz;
    f>>n;
    for(int i=1;i<=n;i++){
        f>>vec[i];
    }
    for(int i=1;i<=n;i++){
        if(vec[i]>new_vec[lung]){
            lung++;
            new_vec[lung]=vec[i];
            father[i]=poz_act[lung-1];
            poz_act[lung]=i;
        }
        else{
            poz=caut_bin(vec[i]);
            new_vec[poz]=vec[i];
            father[i]=poz_act[poz-1];
            poz_act[poz]=i;
        }
    }
    g<<lung<<'\n';
    afisare_rec(poz_act[lung]);
    return 0;
}