Pagini recente » Cod sursa (job #1144341) | Cod sursa (job #332452)
Cod sursa(job #332452)
#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) {
arb[node]=pos;
return ;
}
int m=(l+r)/2;
if (pos<=m) update(2*node, l, m);
else update(2*node+1, m+1, r);
if (v[arb[2*node]]<v[pos+1] && v[arb[2*node+1]]<v[pos+1])
if (best[arb[2*node]]>best[arb[2*node+1]]) arb[node]=arb[2*node];
else arb[node]=arb[2*node+1];
else if (v[arb[2*node]]<v[pos+1]) arb[node]=arb[2*node];
else if (v[arb[2*node+1]]<v[pos+1]) arb[node]=arb[2*node+1];
else arb[node]=0;
}
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]);
v[n+1]=INF;
best[1]=1;
prec[1]=-1;
pos=1;
update(1, 1, n);
for (i=2; i<=n; ++i) {
in=arb[1];
if (!in)
best[i]=1,
prec[i]=-1;
else
best[i]=best[in]+1,
prec[i]=in;
pos=i;
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;
}