Pagini recente » Cod sursa (job #2025800) | Cod sursa (job #1714968) | Cod sursa (job #1984749) | Cod sursa (job #1688968) | Cod sursa (job #710445)
Cod sursa(job #710445)
#include <stdio.h>
#define MAXN 100010
long arb[MAXN], v[100010], n, i, fr[MAXN], sol, af, poz, S[MAXN], h[MAXN];
inline long max(long a, long b) {
if (a < b && b != 2000000000)
return b;
return a;
}
void parc(long st, long dr, long pz) {
if (st == dr) {
if (arb[pz] >= v[i]) {
arb[pz] = v[i];
h[i] = st;
af = 1;
if (fr[st] == 0) {
++sol;
fr[st] = 1;
}
}
return;
}
parc(st, (st + dr) / 2, pz * 2);
arb[pz] = max(arb[pz * 2], arb[pz * 2 + 1]);
if (af == 1) return;
parc((st + dr) / 2 + 1, dr, pz * 2 + 1);
arb[pz] = max(arb[pz * 2], arb[pz * 2 + 1]);
if (af == 1) return;
}
int main() {
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%ld", &n);
for (i = 1; i <= n; ++i) scanf("%ld", &v[i]);
for (i = 1; i < 10000; ++i) arb[i] = 2000000000;
for (i = 1; i <= n; ++i) {
af = 0;
parc(1, n, 1);
}
printf("%ld\n", sol);
long caut = sol;
for (i = n; i >= 1; --i) {
if (caut == h[i]) {
S[++S[0]] = v[i];
--caut;
}
}
for (i = S[0]; i >= 1; --i) printf("%ld ", S[i]);
return 0;
}