Cod sursa(job #1556083)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 24 decembrie 2015 01:50:55
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<fstream>
#include<stack>
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int V[100005], AIB[100005], Index[100005], Sol[100005], El[100005];
int n;

void citire()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>V[i];
}

void Update(int pos)
{
    while(pos <= n){
        AIB[pos] += 1;
        pos += pos&(-pos);
    }
}

int Query(int pos)
{
    int sum = 0;
    while(pos > 0){
        sum += AIB[pos];
        pos -= pos&(-pos);
    }
    return sum;
}

bool Compare(int x, int y)
{
    if(V[x] != V[y])
        return (V[x] < V[y]);
    else
        return x < y;
}

void rez()
{
    int i, ind, maxi = 0, etal, lun = 0, nrel = 0;

    for(i=1; i<=n; i++)
        Index[i] = i;
    sort(Index + 1, Index + n + 1, Compare);

    for(i=1; i<=n; i++){
        Sol[Index[i]] = Query(Index[i]);
        if(V[Index[i]] != V[Index[i-1]]){
            Update(Index[i]);
            Sol[Index[i]]++;
        }
    }

    for(i=1; i<=n; i++)
        if(Sol[i] > maxi){
            maxi = Sol[i];
            ind = i;
    }

    g<<maxi<<"\n";
    El[++nrel] = V[ind];
    maxi--;
    etal = V[ind];

    for(i = ind - 1; i > 0; i--){
        if(Sol[i] == maxi && V[i] < etal){
            maxi--;
            etal = V[i];
            El[++nrel] = etal;
        }
    }

    for(i=nrel; i>0; i--)
        g<<El[i]<<" ";
    g<<"\n";
}

int main()
{
    citire();
    rez();
    return 0;
}