Cod sursa(job #2012180)

Utilizator workwork work work Data 18 august 2017 08:53:42
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

FILE *fin=fopen("scmax.in", "r"), *fout=fopen("scmax.out", "w");

int n, w[100005], sol[100005], poz, p, k[100003], K, st, dr, mij;
pair<int, int> pr[100005];
const int inf = 1 << 30;

int main()
{
    fscanf(fin, "%d ", &n);
    for(int i = 1; i <= n; ++ i) fscanf(fin, "%d ", &w[i]);
    pr[1] = {w[1], 1};
    poz = 1;
    for(int i = 2; i <= n; ++ i)
    {
        st = 1; dr = poz; p = -inf;
        while(st <= dr)
        {
            mij = (st+dr) >> 1;
            if(pr[mij].first >= w[i]) dr = mij-1, p = mij;
            else st = mij+1;
        }
        if(p == -inf)
            pr[++poz] = {w[i], i}, k[i] = pr[poz-1].second;
        else pr[p] = {w[i], i}, k[i] = pr[p-1].second;
    }
    fprintf(fout, "%d\n", poz);
    poz = pr[poz].second;
    while(poz) sol[++K] = poz, poz = k[poz];
    for(int i = K; i > 0; -- i)
        fprintf(fout, "%d ", w[sol[i]]);
    return 0;
}