Cod sursa(job #535383)

Utilizator BitOneSAlexandru BitOne Data 17 februarie 2011 10:02:00
Problema Subsir crescator maximal Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 100011

using namespace std;
int f[N_MAX];
vector< int > v, TopMax;
int main( void )
{
    int N, i, left, middle, right;
    ifstream in( "scmax.in" );
    in>>N;
    copy( istream_iterator<int>(in), istream_iterator<int>(), back_inserter(v) );
    TopMax.push_back(0);
    for( i=1; i < N; ++i )
    {
        left=0; right=TopMax.size()-1;
        while( left < right )
        {
            middle=(left+right)/2;
            if( v[TopMax[middle]] == v[i] )
            {
                left=middle;
                break;
            }
            if( v[TopMax[middle]] > v[i] )
                right=middle;
            else left=middle+1;
        }
        if( v[i] == v[TopMax[left]] )
            continue;
        if( v[TopMax[left]] > v[i] )
        {
            if( left > 0 )
                f[i]=TopMax[left-1];
            TopMax[left]=i;
        }
        else TopMax.push_back(i);
    }
    for( i=TopMax.size()-1; i >= 0; --i )
        TopMax[i]=v[TopMax[i]];
    ofstream out( "scmax.out" );
    out<<TopMax.size()<<'\n';
    copy( TopMax.begin(), TopMax.end(), ostream_iterator<int>( out, " ") );
    out<<'\n';
    return EXIT_SUCCESS;
}