Cod sursa(job #1106636)

Utilizator vlad96Vlad Zuga vlad96 Data 12 februarie 2014 22:55:48
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>

using namespace std;

const int N = 100002;
int n, v[N], p[N], best[N], m[N], maxim, nr, poz;

ofstream g ("scmax.out");

void read ()
{
    ifstream f ("scmax.in");
    f >> n;
    for (int i = 1; i <= n; i ++ )
        f >> v[i];
    f.close();
}

int bs(int x)
{
    int left = 0, right = nr;
    int mid = (left+right)/2;
    while (left <= right)
    {
        if ( v[ m[mid] ] < x && v [ m[mid+1] ] >= x )
            return mid;
        else if ( v[ m[mid+1] ] < x )
        {
            left = mid + 1;
            mid = (left+right)/2;
        }
        else
        {
            right = mid - 1;
            mid = (left+right)/2;
        }
    }
    return nr;
}

void solve ()
{
    best[1] = m[1] = 1, m[0] = 0;
    for (int i = 2; i <= n; i ++ )
    {
        poz = bs(v[i]);
        p[i] = m[poz];
        best[i] = poz + 1;
        m[poz+1] = i;
        if ( nr < poz + 1 )
            nr = poz + 1;
    }

    maxim = poz = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if ( maxim < best[i] )
        {
            maxim = best[i];
            poz = i;
        }
    }
}

void write(int i)
{
    if ( p[i] > 0 )
        write (p[i]);
    g << v[i] << " ";
}

int main()
{
    read();
    solve();
    write(poz);
    return 0;
}