Submission #425164

#	Time	Username	Problem	Language	Result	Execution time	Memory
425164		two_sides	고대 책들 (IOI17_books)	C++17	0 / 100	1 ms	332 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
#define fi first
#define se second

    using ll = long long;

    struct segment_tree {
    #define il i * 2
    #define ir i * 2 + 1

        vector <int> val;
        int n, x, y, res;

        void build(int i, int l, int r,
        const vector <int> &idx) {
            if (l == r) val[i] = idx[l];
            else {
                int m = (l + r) / 2;
                build(il, l, m, idx);
                build(ir, m + 1, r, idx);
                val[i] = max(val[il], val[ir]);
            }
        }

        void init(const vector <int> &idx) {
            n = idx.size();
            val.resize(n * 4);
            build(1, 0, n - 1, idx);
        }

        void rep(int i, int l, int r, int v) {
            if (l == r) val[i] = v;
            else {
                int m = (l + r) / 2;
                if (m >= x) rep(il, l, m, v);
                else rep(ir, m + 1, r, v);
                val[i] = max(val[il], val[ir]);
            }
        }

        void get(int i, int l, int r) {
            if (l >= x && r <= y) {
                res = max(res, val[i]);
                return;
            }
            int m = (l + r) / 2;
            if (m >= x) get(il, l, m);
            if (m < y) get(ir, m + 1, r);
        }

        void rep(int p, int v) {
            x = p; rep(1, 0, n - 1, v);
        }

        int get(int l, int r) {
            x = l; y = r; res = -1;
            get(1, 0, n - 1); return res;
        }
    };

    vector <int> lef, rig, ord;
    vector <vector <int>> own;
    segment_tree seg;
    vector <char> vis;

    void dfs(int u) {
        vis[u] = 1;
        for (int i : own[u]) seg.rep(i, -1);
        int v = seg.get(lef[u], rig[u]);
        while (v >= 0) {
            dfs(v);
            v = seg.get(lef[u], rig[u]);
        }
        ord.push_back(u);
    }
}

ll minimum_walk(vector<int> p, int s) {
    int cnt = 0, n = p.size();
    vector <int> idx(n, -1);
    for (int i = 0; i < n; i++) {
        if (~idx[i]) continue;
        int u = i;
        lef.push_back(i);
        rig.push_back(i);
        own.emplace_back();
        while (idx[u] < 0) {
            own[cnt].push_back(u);
            lef[cnt] = min(lef[cnt], u);
            rig[cnt] = max(rig[cnt], u);
            idx[u] = cnt; u = p[u];
        }
        cnt++;
    }
    vis.assign(n, 0); seg.init(idx);
    for (int u = 0; u < cnt; u++)
        if (!vis[u]) dfs(u);
    reverse(ord.begin(), ord.end());
    vis.assign(n, 0); seg.init(idx);
    vector <pair <int, int>> tmp;
    int mi = s, ma = s;
    for (int u : ord)
        if (!vis[u]) {
            dfs(u); int l = -1, r = n;
            for (int i : own[u]) {
                if (i < s) l = max(l, i);
                if (i > s) r = min(r, i);
            }
            if (l >= 0 && r < n)
                seg.rep(r, r);
            else if (l >= 0)
                mi = min(mi, l);
            else if (r < n)
                ma = max(ma, r);
        }
    sort(tmp.rbegin(), tmp.rend());
    long long res = 2ll *
    (max(ma, seg.val[1]) - mi);
    for (auto &p : tmp) {
        seg.rep(p.se, -1);
        res = min(res, 2ll * (max
        (ma, seg.val[1]) - min(mi, p.fi)));
        swap(p.fi, p.se);
    }
    for (int i = 0; i < n; i++)
        res += abs(i - p[i]);
    return res;
}

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