제출 #425220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425220		two_sides	고대 책들 (IOI17_books)	C++17	0 / 100	2 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 init(int n) {
            this->n = n;
            val.assign(n * 4, -1e9);
        }

        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 = -1e9;
            get(1, 0, n - 1); return res;
        }
    };

    vector <int> lef, rig, scc;
    vector <vector <int>> own, cmp;
    segment_tree seg1, seg2;
    int timer = 0;
    stack <int> stk;
    vector <int> num, low;

    void tarjan(int u) {
        low[u] = num[u] = ++timer;
        for (int i : own[u]) {
            seg1.rep(i, -1);
            seg2.rep(i, -low[u]);
        }
        stk.push(u);
        int v = seg1.get(lef[u], rig[u]);
        while (~v) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            v = seg1.get(lef[u], rig[u]);
        }
        low[u] = min(low[u], -seg2.get(lef[u], rig[u]));
        if (num[u] == low[u]) {
            cmp.emplace_back();
            do {
                v = stk.top(); stk.pop();
                cmp.back().push_back(v);
                scc[v] = cmp.size() - 1;
                num[v] = low[v] = 1e9;
            } while (v != 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++;
    }
    scc.resize(cnt);
    num.resize(cnt); low.resize(cnt);
    seg1.init(idx); seg2.init(n);
    for (int i = 0; i < cnt; i++)
        if (!num[i]) tarjan(i);
    num.assign(cmp.size(), 0);
    vector <pair <int, int>> tmp;
    int mi = s, ma = s;
    seg1.init(idx); seg2.init(n);
    for (int i = cmp.size() - 1; i >= 0; i--) {
        if (!num[i]) {
            int l = -1, r = n;
            for (int j : cmp[i])
                for (int k : own[j]) {
                    if (k <= s) l = max(l, k);
                    if (k >= s) r = min(r, k);
                    seg1.rep(k, -1);
                }
            if (l >= 0 && r < n) {
                tmp.emplace_back(l, r);
                seg2.rep(r, r);
            } else if (l >= 0) mi = min(mi, l);
            else if (r < n) ma = max(ma, r);
        }
        for (int j : cmp[i])
            for (int k : own[j])
                seg1.rep(k, -1);
        for (int j : cmp[i]) {
            int k = seg1.get(lef[j], rig[j]);
            while (k >= 0) {
                num[scc[k]] = true;
                for (int l : own[k])
                    seg1.rep(l, -1);
                k = seg1.get(lef[j], rig[j]);
            }
        }
    }
    sort(tmp.rbegin(), tmp.rend());
    long long res = 2ll * (max(ma, seg2.val[1]) - mi);
    for (auto &p : tmp) {
        seg2.rep(p.se, -1);
        res = min(res, 2ll * (max(ma, seg2.val[1]) - min(mi, p.fi)));
    }
    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