Submission #790570

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790570	2023-07-22T21:01:15 Z	skittles1412	Ancient Books (IOI17_books)	C++17	100 / 100	1491 ms	270696 KB

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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	65896 KB	Output is correct
2	Correct	27 ms	65940 KB	Output is correct
3	Correct	26 ms	65916 KB	Output is correct
4	Correct	26 ms	65876 KB	Output is correct
5	Correct	25 ms	65876 KB	Output is correct
6	Correct	27 ms	65964 KB	Output is correct
7	Correct	30 ms	65876 KB	Output is correct
8	Correct	30 ms	65916 KB	Output is correct
9	Correct	26 ms	65956 KB	Output is correct
10	Correct	26 ms	65944 KB	Output is correct
11	Correct	26 ms	65876 KB	Output is correct
12	Correct	26 ms	65848 KB	Output is correct
13	Correct	26 ms	65876 KB	Output is correct
14	Correct	26 ms	65960 KB	Output is correct
15	Correct	27 ms	65892 KB	Output is correct
16	Correct	27 ms	65908 KB	Output is correct
17	Correct	27 ms	65952 KB	Output is correct
18	Correct	26 ms	65964 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	65896 KB	Output is correct
2	Correct	27 ms	65940 KB	Output is correct
3	Correct	26 ms	65916 KB	Output is correct
4	Correct	26 ms	65876 KB	Output is correct
5	Correct	25 ms	65876 KB	Output is correct
6	Correct	27 ms	65964 KB	Output is correct
7	Correct	30 ms	65876 KB	Output is correct
8	Correct	30 ms	65916 KB	Output is correct
9	Correct	26 ms	65956 KB	Output is correct
10	Correct	26 ms	65944 KB	Output is correct
11	Correct	26 ms	65876 KB	Output is correct
12	Correct	26 ms	65848 KB	Output is correct
13	Correct	26 ms	65876 KB	Output is correct
14	Correct	26 ms	65960 KB	Output is correct
15	Correct	27 ms	65892 KB	Output is correct
16	Correct	27 ms	65908 KB	Output is correct
17	Correct	27 ms	65952 KB	Output is correct
18	Correct	26 ms	65964 KB	Output is correct
19	Correct	27 ms	66100 KB	Output is correct
20	Correct	27 ms	66004 KB	Output is correct
21	Correct	25 ms	65980 KB	Output is correct
22	Correct	27 ms	65944 KB	Output is correct
23	Correct	28 ms	65980 KB	Output is correct
24	Correct	29 ms	65920 KB	Output is correct
25	Correct	32 ms	66020 KB	Output is correct
26	Correct	27 ms	66004 KB	Output is correct
27	Correct	27 ms	66020 KB	Output is correct
28	Correct	28 ms	65964 KB	Output is correct
29	Correct	27 ms	66004 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	65896 KB	Output is correct
2	Correct	27 ms	65940 KB	Output is correct
3	Correct	26 ms	65916 KB	Output is correct
4	Correct	26 ms	65876 KB	Output is correct
5	Correct	25 ms	65876 KB	Output is correct
6	Correct	27 ms	65964 KB	Output is correct
7	Correct	30 ms	65876 KB	Output is correct
8	Correct	30 ms	65916 KB	Output is correct
9	Correct	26 ms	65956 KB	Output is correct
10	Correct	26 ms	65944 KB	Output is correct
11	Correct	26 ms	65876 KB	Output is correct
12	Correct	26 ms	65848 KB	Output is correct
13	Correct	26 ms	65876 KB	Output is correct
14	Correct	26 ms	65960 KB	Output is correct
15	Correct	27 ms	65892 KB	Output is correct
16	Correct	27 ms	65908 KB	Output is correct
17	Correct	27 ms	65952 KB	Output is correct
18	Correct	26 ms	65964 KB	Output is correct
19	Correct	27 ms	66100 KB	Output is correct
20	Correct	27 ms	66004 KB	Output is correct
21	Correct	25 ms	65980 KB	Output is correct
22	Correct	27 ms	65944 KB	Output is correct
23	Correct	28 ms	65980 KB	Output is correct
24	Correct	29 ms	65920 KB	Output is correct
25	Correct	32 ms	66020 KB	Output is correct
26	Correct	27 ms	66004 KB	Output is correct
27	Correct	27 ms	66020 KB	Output is correct
28	Correct	28 ms	65964 KB	Output is correct
29	Correct	27 ms	66004 KB	Output is correct
30	Correct	1491 ms	270380 KB	Output is correct
31	Correct	1419 ms	270696 KB	Output is correct
32	Correct	649 ms	164152 KB	Output is correct
33	Correct	650 ms	148852 KB	Output is correct
34	Correct	653 ms	148804 KB	Output is correct
35	Correct	657 ms	140616 KB	Output is correct
36	Correct	718 ms	132760 KB	Output is correct
37	Correct	839 ms	144644 KB	Output is correct
38	Correct	878 ms	156464 KB	Output is correct
39	Correct	894 ms	158648 KB	Output is correct
40	Correct	997 ms	179524 KB	Output is correct
41	Correct	1273 ms	229988 KB	Output is correct
42	Correct	1176 ms	218876 KB	Output is correct
43	Correct	767 ms	161944 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	66012 KB	Output is correct
2	Correct	27 ms	66004 KB	Output is correct
3	Correct	27 ms	66036 KB	Output is correct
4	Correct	26 ms	66004 KB	Output is correct
5	Correct	27 ms	66004 KB	Output is correct
6	Correct	28 ms	65948 KB	Output is correct
7	Correct	28 ms	65996 KB	Output is correct
8	Correct	29 ms	65988 KB	Output is correct
9	Correct	28 ms	65976 KB	Output is correct
10	Correct	29 ms	66008 KB	Output is correct
11	Correct	28 ms	66032 KB	Output is correct
12	Correct	29 ms	66056 KB	Output is correct
13	Correct	29 ms	65920 KB	Output is correct
14	Correct	28 ms	66000 KB	Output is correct
15	Correct	31 ms	66000 KB	Output is correct
16	Correct	28 ms	65980 KB	Output is correct
17	Correct	28 ms	65988 KB	Output is correct
18	Correct	28 ms	65940 KB	Output is correct
19	Correct	29 ms	65932 KB	Output is correct
20	Correct	28 ms	65948 KB	Output is correct

Subtask #5

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	65896 KB	Output is correct
2	Correct	27 ms	65940 KB	Output is correct
3	Correct	26 ms	65916 KB	Output is correct
4	Correct	26 ms	65876 KB	Output is correct
5	Correct	25 ms	65876 KB	Output is correct
6	Correct	27 ms	65964 KB	Output is correct
7	Correct	30 ms	65876 KB	Output is correct
8	Correct	30 ms	65916 KB	Output is correct
9	Correct	26 ms	65956 KB	Output is correct
10	Correct	26 ms	65944 KB	Output is correct
11	Correct	26 ms	65876 KB	Output is correct
12	Correct	26 ms	65848 KB	Output is correct
13	Correct	26 ms	65876 KB	Output is correct
14	Correct	26 ms	65960 KB	Output is correct
15	Correct	27 ms	65892 KB	Output is correct
16	Correct	27 ms	65908 KB	Output is correct
17	Correct	27 ms	65952 KB	Output is correct
18	Correct	26 ms	65964 KB	Output is correct
19	Correct	27 ms	66100 KB	Output is correct
20	Correct	27 ms	66004 KB	Output is correct
21	Correct	25 ms	65980 KB	Output is correct
22	Correct	27 ms	65944 KB	Output is correct
23	Correct	28 ms	65980 KB	Output is correct
24	Correct	29 ms	65920 KB	Output is correct
25	Correct	32 ms	66020 KB	Output is correct
26	Correct	27 ms	66004 KB	Output is correct
27	Correct	27 ms	66020 KB	Output is correct
28	Correct	28 ms	65964 KB	Output is correct
29	Correct	27 ms	66004 KB	Output is correct
30	Correct	1491 ms	270380 KB	Output is correct
31	Correct	1419 ms	270696 KB	Output is correct
32	Correct	649 ms	164152 KB	Output is correct
33	Correct	650 ms	148852 KB	Output is correct
34	Correct	653 ms	148804 KB	Output is correct
35	Correct	657 ms	140616 KB	Output is correct
36	Correct	718 ms	132760 KB	Output is correct
37	Correct	839 ms	144644 KB	Output is correct
38	Correct	878 ms	156464 KB	Output is correct
39	Correct	894 ms	158648 KB	Output is correct
40	Correct	997 ms	179524 KB	Output is correct
41	Correct	1273 ms	229988 KB	Output is correct
42	Correct	1176 ms	218876 KB	Output is correct
43	Correct	767 ms	161944 KB	Output is correct
44	Correct	26 ms	66012 KB	Output is correct
45	Correct	27 ms	66004 KB	Output is correct
46	Correct	27 ms	66036 KB	Output is correct
47	Correct	26 ms	66004 KB	Output is correct
48	Correct	27 ms	66004 KB	Output is correct
49	Correct	28 ms	65948 KB	Output is correct
50	Correct	28 ms	65996 KB	Output is correct
51	Correct	29 ms	65988 KB	Output is correct
52	Correct	28 ms	65976 KB	Output is correct
53	Correct	29 ms	66008 KB	Output is correct
54	Correct	28 ms	66032 KB	Output is correct
55	Correct	29 ms	66056 KB	Output is correct
56	Correct	29 ms	65920 KB	Output is correct
57	Correct	28 ms	66000 KB	Output is correct
58	Correct	31 ms	66000 KB	Output is correct
59	Correct	28 ms	65980 KB	Output is correct
60	Correct	28 ms	65988 KB	Output is correct
61	Correct	28 ms	65940 KB	Output is correct
62	Correct	29 ms	65932 KB	Output is correct
63	Correct	28 ms	65948 KB	Output is correct
64	Correct	691 ms	155920 KB	Output is correct
65	Correct	724 ms	161936 KB	Output is correct
66	Correct	855 ms	152968 KB	Output is correct
67	Correct	904 ms	158648 KB	Output is correct
68	Correct	84 ms	74068 KB	Output is correct
69	Correct	89 ms	74040 KB	Output is correct
70	Correct	85 ms	74340 KB	Output is correct
71	Correct	79 ms	74672 KB	Output is correct
72	Correct	79 ms	75680 KB	Output is correct
73	Correct	104 ms	77968 KB	Output is correct
74	Correct	631 ms	155276 KB	Output is correct
75	Correct	641 ms	155200 KB	Output is correct
76	Correct	800 ms	165544 KB	Output is correct
77	Correct	762 ms	168492 KB	Output is correct
78	Correct	739 ms	158000 KB	Output is correct
79	Correct	755 ms	157972 KB	Output is correct
80	Correct	624 ms	170572 KB	Output is correct
81	Correct	908 ms	223528 KB	Output is correct
82	Correct	921 ms	223504 KB	Output is correct
83	Correct	755 ms	147920 KB	Output is correct
84	Correct	758 ms	139880 KB	Output is correct
85	Correct	765 ms	139356 KB	Output is correct
86	Correct	863 ms	143184 KB	Output is correct
87	Correct	825 ms	192972 KB	Output is correct
88	Correct	790 ms	170596 KB	Output is correct
89	Correct	758 ms	152220 KB	Output is correct
90	Correct	926 ms	150952 KB	Output is correct
91	Correct	1014 ms	159112 KB	Output is correct
92	Correct	979 ms	178916 KB	Output is correct