Submission #119702

#	Time	Username	Problem	Language	Result	Execution time	Memory
119702		thebes	Ancient Books (IOI17_books)	C++14	50 / 100	933 ms	99192 KiB

books

#include <bits/stdc++.h>
using namespace std;

const int MN = 1e6+6;
typedef long long ll;
ll n, m, s, i, j, l[MN], r[MN], id[MN], arr[MN], vis[MN], vs[MN], ac[MN], nxt, ans, L, R, _l[MN], _r[MN];
vector<int> res, ress; set<int> avail;

void dfs(ll n){
    ans += abs(n-arr[n]);
    l[id[n]]=min(l[id[n]],n);
    r[id[n]]=max(r[id[n]],n);
    if(id[arr[n]]) return;
    id[arr[n]]=id[n];
    dfs(arr[n]);
}

void ddfs(ll n,ll p=0){
    if(vs[n]) return;
    res.push_back(n); vs[n]=1;
    vector<int> to;
    auto it = avail.lower_bound(l[n]);
    while(it!=avail.end()&&*it<=r[n]){
        int v = *it; ress.push_back(v);
        auto it2 = it; it++;
        avail.erase(it2);
        if(!vs[id[v]]) to.push_back(id[v]);
    }
    for(auto v : to) ddfs(v, p);
    if(p) L=min(L,l[n]), R=max(R,r[n]);
}

ll minimum_walk(vector<int> p,int e){
    n = p.size(); s = e+1;
    for(i=0;i<n;i++) arr[i+1]=p[i]+1;
    for(i=1;i<=n;i++){
        avail.insert(i);
        l[i] = 1<<30;
        if(!id[i]){
            id[i] = ++nxt;
            dfs(i);
        }
    }
    for(i=1;i<=nxt;i++){
        if(l[i]!=r[i]) ac[++m]=i;
    }
    L = R = s;
    while(1){
        ll LL, RR;
        for(i=_r[R];i+R<=n&&(arr[i+R]==i+R||vs[id[i+R]]);i++){}
        RR = i+R; _r[R] = i;
        for(i=_l[L];L-i>=1&&(arr[L-i]==L-i||vs[id[L-i]]);i++){}
        LL = L-i; _l[L] = i;
        if(RR<=n&&LL>=1){
            int wth = 0;
            if(abs(RR-R)>abs(LL-L)) swap(LL,RR), wth=1;
            ddfs(id[RR]);
            if(vs[id[LL]]){
                if(!wth) ans += 2*abs(RR-R);
                else ans += 2*abs(RR-L);
                for(auto v : res) vs[v]=0;
                for(auto v : ress) avail.insert(v);
                res.clear(); ress.clear();
                ddfs(id[RR],1);
                res.clear(); ress.clear();
                continue;
            }
            if(!wth) ans += 2*abs(L-LL);
            else ans += 2*abs(R-LL);
            ddfs(id[LL],1);
            res.clear(); ress.clear();
        }
        else if(RR<=n){
            ans += 2*(RR-R);
            ddfs(id[RR], 1);
            res.clear(); ress.clear();
        }
        else if(LL>=1){
            ans += 2*(L-LL);
            ddfs(id[LL], 1);
            res.clear(); ress.clear();
        }
        else break;
    }
    return ans;
}

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