Submission #119676

#	Time	Username	Problem	Language	Result	Execution time	Memory
119676		thebes	Ancient Books (IOI17_books)	C++14	50 / 100	309 ms	58616 KiB

books

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

const int MN = 1e6+6;
typedef long long ll;
ll n, s, i, arr[MN], id[MN], j, ans, nxt, L, R, ord[MN], sz, rb, SZ, wew[MN];
struct cyc{ll l, r, a, b;}a[MN];

void dfs(ll n){
    ans += abs(arr[n]-n);
    a[id[n]].l=min(a[id[n]].l,n);
    a[id[n]].r=max(a[id[n]].r,n);
    if(n<=s) a[id[n]].a=max(a[id[n]].a,n);
    if(n>=s) a[id[n]].b=min(a[id[n]].b,n);
    if(id[arr[n]]) return;
    id[arr[n]] = id[n];
    dfs(arr[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++){
        a[i].l=1000000000,a[i].b=1000000000;
        a[i].a=-1000000000,a[i].r=-1000000000;
    }
    for(i=1;i<=n;i++) if(!id[i]) id[i]=++nxt, dfs(i);
    for(i=1;i<=nxt;i++){
        if(a[i].l!=a[i].r){
            ord[++sz] = i;
        }
    }
    sort(ord+1,ord+sz+1,[](ll i,ll j){return a[i].l<a[j].l;});
    R = 0;
    for(i=1;i<=sz;i++){
        if(a[ord[i]].r<=R) continue;
        R = a[ord[i]].r;
        wew[++SZ] = ord[i];
    }
    sort(wew+1,wew+SZ+1,[](ll i,ll j){return min(a[i].b-s,s-a[i].a)<min(a[j].b-s,s-a[j].a);});
    L = R = s;
    for(i=1;i<=SZ;i++){
        ans += 2*max(0LL,min(L-a[wew[i]].a,a[wew[i]].b-R));
        L = min(a[wew[i]].l, L);
        R = max(a[wew[i]].r, R);
    }
    return ans;
}

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