Pagini recente » Cod sursa (job #483970) | Cod sursa (job #235386) | Cod sursa (job #2033366) | Cod sursa (job #1461069) | Cod sursa (job #332449)
Cod sursa(job #332449)
#include <stdio.h>
#define MAXN 100001
#define MAXARBN 1<<20
#define INF 2000000001
int n, v[MAXN], best[MAXN], prec[MAXN], ct, sol[MAXN];
int arb[MAXARBN], start, end, pos;
void update(int node, int l, int r) {
if (l==r) {
if (l<pos && v[l]<v[pos]) arb[node]=l;
else arb[node]=0;
/*if (l<pos) arb[node]=best[l];
else arb[node]=0;*/
return ;
}
int m=(l+r)/2;
update(2*node, l, m);
update(2*node+1, m+1, r);
if (best[arb[2*node]]>best[arb[2*node+1]]) arb[node]=arb[2*node];
else arb[node]=arb[2*node+1];
/*if (arb[2*node]>arb[2*node+1]) arb[node]=arb[2*node];
else arb[node]=arb[2*node+1];*/
}
int main() {
int i, in;
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%d\n", &n);
for (i=1; i<=n; ++i) scanf("%d\n", &v[i]);
best[1]=1;
prec[1]=-1;
for (i=2; i<=n; ++i) {
pos=i;
update(1, 1, n);
in=arb[1];
if (!in)
best[i]=1,
prec[i]=-1;
else
best[i]=best[in]+1,
prec[i]=in;
}
pos=n+1;
v[n+1]=INF;
update(1, 1, n);
in=arb[1];
ct=0;
while (in>0)
sol[++ct]=v[in],
in=prec[in];
printf("%d\n", ct);
for (i=ct; i; --i) printf("%d ", sol[i]);
printf("\n");
return 0;
}