Cod sursa(job #1181300)

Utilizator assa98Andrei Stanciu assa98 Data 2 mai 2014 13:58:09
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define pe pair<int,int>
#define mp make_pair
#define fi first
#define se second

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

const int MAX_N=100100;

inline bool cmp( const pe &a, const pe &b ) {
    if( a.fi == b.fi ) {
        return a.se < b.se;
    }
    return a.fi < b.fi;
}

int v[MAX_N];
int d[MAX_N];
vector< pe > a;
int aib[MAX_N];
int n;

void update(int poz, int val) {
    while ( poz <= n ) {
        aib[poz] += val;
        poz += ( poz & ( -poz ) );
    }
}

int query(int poz) {
    int sum = 0;
    while( poz ) {
        sum += aib[poz];
        poz -= ( poz & ( -poz ) );
    }
    return sum;
}

int main() {
    fin>>n;
    for( int i=1; i<=n; i++) {
        fin >> v[i];
        a.push_back( mp( v[i], i ) );
    }

    sort( a.begin(), a.end(), cmp );
    
    update(a[0].se,1);
    d[a[0].se]=1;
    for(auto i = 1; i < (int) a.size(); i++) {
        if(a[i].fi==a[i-1].fi) {
            d[a[i].se]=d[a[i-1].se];
            continue;
        }
        update( a[i].se, 1 );
        d[ a[i].se ] = query( a[i].se );
    }

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

    fout << d[poz]<<'\n';

    vector<int> sol;
    sol.push_back(v[poz]);
    for(int i=poz-1; i>=1 && d[poz]>1; i--) {
        if( d[i]+1 == d[poz] && v[i] < v[poz] ) {
            poz=i;
            sol.push_back(v[poz]);
        }
    }

    reverse(sol.begin(), sol.end());
    for(auto it=sol.begin(); it!=sol.end(); it++) {
        fout<<*it<<' ';
    }

    return 0;
}