Submission #790570

#	Time	Username	Problem	Language	Result	Execution time	Memory
790570		skittles1412	Ancient Books (IOI17_books)	C++17	100 / 100	1491 ms	270696 KiB

books

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct DFS1 {
    int n;
    set<int> to_vis;
    vector<char> vis;
    vector<int> arr, ord;

    DFS1(const vector<int>& arr) : n(sz(arr)), vis(n), arr(arr) {
        for (int i = 0; i < n; i++) {
            to_vis.insert(i);
        }
    }

    void dfs(int u) {
        assert(!vis[u]);
        vis[u] = true;
        to_vis.erase(u);

        int ql = arr[u], qr = u;
        if (ql > qr) {
            swap(ql, qr);
        }

        while (true) {
            auto it = to_vis.lower_bound(ql);
            if (it == to_vis.end() || *it > qr) {
                break;
            }
            dfs(*it);
        }
        ord.push_back(u);
    }
};

basic_string<int> v[1 << 21];

struct ST1 {
    int n;

    ST1(int n) : n(n) {}

    void update(int o, int l, int r, int ql, int qr, int x) {
        if (ql <= l && r <= qr) {
            v[o].push_back(x);
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, x);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, x);
        }
    }

    void update(int l, int r, int x) {
        update(1, 0, n - 1, l, r, x);
    }

    template <typename Cb>
    void query(int o, int l, int r, int ind, const Cb& cb) {
        while (sz(v[o])) {
            int cx = v[o].back();
            v[o].pop_back();
            cb(cx);
        }
        if (l == r) {
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ind <= mid) {
            query(lc, l, mid, ind, cb);
        } else {
            query(rc, mid + 1, r, ind, cb);
        }
    }

    template <typename Cb>
    void query(int ind, const Cb& cb) {
        query(1, 0, n - 1, ind, cb);
    }
};

struct DFS2 {
    int n;
    vector<char> vis;
    vector<int> ord;
    ST1 st;

    DFS2(const vector<int>& arr) : n(sz(arr)), vis(n), st(n) {
        for (int i = 0; i < n; i++) {
            int ql = arr[i], qr = i;
            if (ql > qr) {
                swap(ql, qr);
            }
            st.update(ql, qr, i);
        }
    }

    void dfs(int u) {
        assert(!vis[u]);
        vis[u] = true;
        st.query(u, [&](int v) -> void {
            if (!vis[v]) {
                dfs(v);
            }
        });
        ord.push_back(u);
    }
};

vector<vector<int>> scc(const vector<int>& arr) {
    int n = sz(arr);

    DFS1 dfs1(arr);
    for (int i = 0; i < n; i++) {
        if (dfs1.vis[i]) {
            continue;
        }
        dfs1.dfs(i);
    }
    auto ord = dfs1.ord;
    reverse(begin(ord), end(ord));

    DFS2 dfs2(arr);
    vector<vector<int>> comps;
    for (auto& a : ord) {
        if (dfs2.vis[a]) {
            continue;
        }
        dfs2.ord.clear();
        dfs2.dfs(a);
        comps.push_back(dfs2.ord);
    }

    return comps;
}

int n;
vector<int> cl, cr, l_len, l_v, r_len, r_v;
vector<long> memo;

long dp(int ind) {
    long& ans = memo[ind];
    if (ans != -1) {
        return ans;
    }

    if (l_v[ind] == -1 && r_v[ind] == -1) {
        return l_len[ind] + r_len[ind];
    }

    ans = 1e18;

    if (l_v[ind] != -1) {
        ans = min(ans, l_len[ind] + dp(l_v[ind]));
    }
    if (r_v[ind] != -1) {
        ans = min(ans, r_len[ind] + dp(r_v[ind]));
    }

    return ans;
}

ll minimum_walk(vector<int> arr, int kv) {
    n = sz(arr);

    if (n == 1) {
        return 0;
    }

    auto comps = scc(arr);

    for (auto& a : comps) {
        for (auto& b : a) {
            cerr << b << " ";
        }
        cerr << endl;
    }

    cl = vector<int>(n, n);
    cr = vector<int>(n, -1);

    for (int it = sz(comps) - 1; it >= 0; it--) {
        auto& comp = comps[it];
        int ql = n, ml = n, qr = 0, mr = 0;

        for (auto& a : comp) {
            ml = min(ml, a);
            mr = max(mr, a);
            ql = min(ql, arr[a]);
            qr = max(qr, arr[a]);
        }

        ml = min(ml, ql);
        mr = max(mr, qr);

        for (auto& a : comp) {
            cl[a] = ml;
            cr[a] = mr;
        }
    }

    int sort_p, sort_s;
    for (sort_p = 0; sort_p < n && arr[sort_p] == sort_p; sort_p++)
        ;
    for (sort_s = n - 1; sort_s >= 0 && arr[sort_s] == sort_s; sort_s--)
        ;

    l_len = vector<int>(n);
    l_v = vector<int>(n);
    r_len = vector<int>(n);
    r_v = vector<int>(n);

    {
        fill(l_v.begin(), l_v.begin() + min(n, sort_p + 1), -1);
        for (int i = sort_p + 1; i < n; i++) {
            int ql = cl[i], qr = cr[i];

            if (ql <= sort_p) {
                l_len[i] = 0;
                l_v[i] = -1;
                continue;
            }

            if (qr < cr[ql - 1]) {
                l_len[i] = 1;
                l_v[i] = ql - 1;
                continue;
            }

            int plen = l_len[ql - 1], pv = l_v[ql - 1];
            if (pv == -1) {
                l_len[i] = plen + 1;
                l_v[i] = -1;
                continue;
            }

            if (qr < cr[pv]) {
                l_len[i] = plen + 1;
                l_v[i] = pv;
                continue;
            }

            l_len[i] = plen + 1 + l_len[pv];
            l_v[i] = l_v[pv];
        }
    }
    {
        fill(r_v.begin() + max(0, sort_s), r_v.end(), -1);
        for (int i = sort_s - 1; i >= 0; i--) {
            int ql = cl[i], qr = cr[i];

            if (sort_s <= qr) {
                r_len[i] = 0;
                r_v[i] = -1;
                continue;
            }

            if (cl[qr + 1] < ql) {
                r_len[i] = 1;
                r_v[i] = qr + 1;
                continue;
            }

            int plen = r_len[qr + 1], pv = r_v[qr + 1];
            if (pv == -1) {
                r_len[i] = plen + 1;
                r_v[i] = -1;
                continue;
            }

            if (cl[pv] < ql) {
                r_len[i] = plen + 1;
                r_v[i] = pv;
                continue;
            }

            r_len[i] = plen + 1 + r_len[pv];
            r_v[i] = r_v[pv];
        }
    }

    for (int i = 0; i < n; i++) {
        dbg(i, cl[i], cr[i], l_len[i], l_v[i], r_len[i], r_v[i]);
    }

    long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += 2 * max(0, arr[i] - i);
    }

    memo = vector<long>(n, -1);
    dbg(dp(kv));
    ans += 2 * dp(kv);

    return ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30