Cod sursa(job #3337389)

Utilizator vladneaguVladneagu vladneagu Data 27 ianuarie 2026 16:21:08
Problema Distincte Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 300000 + 5;

struct Node {
    int val, from;
};

Node seg[4 * MAXN], lazy[4 * MAXN];
int a[MAXN], b[MAXN];
int dp[MAXN], parent_depth[MAXN];
int n;

Node merge(Node A, Node B) {
    if (A.val < B.val) return A;
    return B;
}

void apply(int v, Node x) {
    if (x.val < seg[v].val) {
        seg[v] = x;
        lazy[v] = x;
    }
}

void push(int v) {
    if (lazy[v].val != INF) {
        apply(v << 1, lazy[v]);
        apply(v << 1 | 1, lazy[v]);
        lazy[v] = {INF, -1};
    }
}

void build(int v, int l, int r) {
    seg[v] = lazy[v] = {INF, -1};
    if (l == r) return;
    int m = (l + r) >> 1;
    build(v << 1, l, m);
    build(v << 1 | 1, m + 1, r);
}

void update(int v, int l, int r, int ql, int qr, Node x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        apply(v, x);
        return;
    }
    push(v);
    int m = (l + r) >> 1;
    update(v << 1, l, m, ql, qr, x);
    update(v << 1 | 1, m + 1, r, ql, qr, x);
    seg[v] = merge(seg[v << 1], seg[v << 1 | 1]);
}

Node query(int v, int l, int r, int pos) {
    if (l == r) return seg[v];
    push(v);
    int m = (l + r) >> 1;
    if (pos <= m) return query(v << 1, l, m, pos);
    return query(v << 1 | 1, m + 1, r, pos);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    build(1, 0, n);

    // Base case: from depth 0, we are already at ground
    dp[0] = 0;

    // Initialize segment tree with dp[0]
    update(1, 0, n, 0, 0, {0, 0});

    for (int y = 0; y <= n; y++) {
        int z = (y == 0 ? 0 : y + b[y]);
        if (z > n) continue;

        Node best = query(1, 0, n, z);
        if (best.val == INF) continue;

        int L = max(0, y);
        int R = min(n, y + a[y]);

        update(1, 0, n, L, R, {best.val + 1, y});
    }

    Node ans = query(1, 0, n, n);
    if (ans.val == INF) {
        cout << -1 << '\n';
        return 0;
    }

    cout << ans.val << '\n';

    // Reconstruct
    vector<int> jumps;
    int cur = n;
    while (cur != 0) {
        Node here = query(1, 0, n, cur);
        int y = here.from;
        jumps.push_back(y);
        cur = y + b[y];
    }

    reverse(jumps.begin(), jumps.end());
    for (int x : jumps) cout << x << " ";
    cout << '\n';

    return 0;
}