Submission #1201071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201071		badge881	Ancient Books (IOI17_books)	C++20	100 / 100	627 ms	102176 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#define int long long
using namespace std;

const int maxn = 1e6 + 5, INF = 1e18;
int n;
int p[maxn], ll[maxn], rr[maxn], vis[maxn];

int fa[maxn], sz[maxn];
int rt(int u) {
    if (fa[u] == u) return u;
    return fa[u] = rt(fa[u]);
}
void merge(int u, int v) {
    u = rt(u), v = rt(v);
    if (u == v) return;
    if (sz[u] > sz[v]) swap(u, v);
    fa[u] = v; 
    sz[v] += sz[u];
    ll[v] = min(ll[u], ll[v]);
    rr[v] = max(rr[u], rr[v]);
}

int minimum_walk(vector<int32_t> P, int32_t S) {
    n = P.size();
    for (int i=0;i<n;i++) p[i+1] = P[i] + 1;
    S++;
    for (int i=0;i<=n+1;i++) ll[i] = rr[i] = fa[i] = i, sz[i] = 1;
    int ans = 0, cnt = 0;
    for (int i=1;i<=n;i++) if (!vis[i]) {
        int u = i;
        while (true) {
            merge(u, i);
            vis[u] = true;
            int v = p[u];
            ans += abs(v-u);
            if (v==i) break;
            u = v;
        }
    }
    set<int> s;
    s.insert(INF);
    for (int i=1;i<=n;i++) if (ll[rt(i)] == i) {
        int u = i, lim = rr[rt(i)];
        vector<int> log;
        while (s.size() > 0) {
            int pos = *s.lower_bound(u);
            if (pos > lim) break;
            log.push_back(rt(pos));
            u = rr[rt(pos)] + 1;
        }
        for (int j:log) merge(j, i);
        u = i;
        while (true) {
            s.insert(u);
            int v = p[u];
            if (v == i) break;
            u = v;
        }
    }
 
    int lend = 1, rend = n;
    while (lend+1 <= n && p[lend] == lend) lend++;
    while (rend-1 >= 1 && p[rend] == rend) rend--;

    int l = ll[rt(S)], r = rr[rt(S)];
    if (l >= lend && r <= rend) {
        merge(lend-1, rend+1);
        while (l >= lend && r <= rend) {
            int lcost = 0, rcost = 0;
            int lu = l;
            while (rr[rt(lu)] <= r) {
                lu = ll[rt(lu - 1)], lcost += 2;
            }
            if (lu == lend-1) lcost = INF;
            int ru = r;
            while (ll[rt(ru)] >= l) {
                ru = rr[rt(ru + 1)], rcost += 2;
            }
            if (ru == rend+1) rcost = INF;
            // cout << l << " " << r << endl;
            if (lcost == INF && rcost == INF) break;
            if (lcost < rcost) ans += lcost, l = ll[rt(lu)], r = rr[rt(lu)];
            else ans += rcost, l = ll[rt(ru)], r = rr[rt(ru)];
        }
    }
    while (l > lend) l = ll[rt(l-1)], ans += 2;
    while (r < rend) r = rr[rt(r+1)], ans += 2;
    return ans;
}

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