Pagini recente » Cod sursa (job #242224) | Cod sursa (job #415047) | Cod sursa (job #814059) | Cod sursa (job #78072) | Cod sursa (job #1941566)
#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;
}