Cod sursa(job #1941566)

Utilizator mateibanuBanu Matei Costin mateibanu Data 27 martie 2017 14:11:38
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

FILE*f=fopen("scmax.in","r");
FILE*g=fopen("scmax.out","w");

int v[100010],p[100010],l[100010],nx[100010],n;

struct pct{
    int p,x;
}a[100010];

int cmp(pct a,pct b){
    return a.x<b.x;
}

int cauta(int pr, int u, int x, int i)
{
    int m;
    while (pr<u){
        m=(pr+u)/2;
        if (a[m].x<=x) pr=m+1;
        else if (a[m].x==x&&a[m].p<=i) pr=m+1;
            else u=m;
    }
    if (a[u+1].x>x||u+1>n) u--;
    return u+1;
}

int main()
{
    int i,mx;
    fscanf(f,"%d",&n);
    for (i=1;i<=n;i++) {fscanf(f,"%d",&v[i]);a[i].x=v[i];a[i].p=i;}
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++) p[a[i].p]=i;
    l[n]=1;mx=n;
    nx[n]=n+1;
    for (i=n-1;i>=1;i--){
        nx[i]=cauta(p[i]+1,n,a[p[i]].x,i);
        l[i]=l[a[nx[i]].p]+1;
        if (l[i]>l[mx]) mx=i;
    }
    i=p[mx];
    fprintf(g,"%d\n",l[mx]);
    while (i!=n+1){
        fprintf(g,"%d ",a[i].x);
        i=nx[a[i].p];
    }
    fclose(f);
    fclose(g);
    return 0;
}