Submission #1047845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047845		Ahmed57	Ancient Books (IOI17_books)	C++17	100 / 100	92 ms	34752 KiB

books

#include "bits/stdc++.h"
using namespace std;
vector<int> P;
int vis[1000001];
int vis2[1000001];
int L[1000001];
int R[1000001];
int mn = 1e9 ,mx = -1e9;
void dfs(int i){
    vis[i] = 1;
    mn = min(mn,i);
    mx = max(mx,i);
    if(!vis[P[i]])dfs(P[i]);
}
void DFS(int i){
    L[i] = mn;
    R[i] = mx;
    vis2[i] = 1;
    if(!vis2[P[i]])DFS(P[i]);
}
void extend(int &l,int &r){
    int mnl = l;
    int mnr = r;
    mnl = min({mnl,L[l],L[r]});
    mnr = max({mnr,R[r],R[l]});
    while(l>mnl||r<mnr){
        if(l>mnl){
            l--;
            mnl = min(mnl,L[l]);
            mnr = max(mnr,R[l]);
        }else{
            r++;
            mnl = min(mnl,L[r]);
            mnr = max(mnr,R[r]);
        }
    }
}
int get(int l,int r,int targl,int targr){
    extend(l,r);
    int all = 0;
    while(l>targl||r<targr){
        extend(l,r);
        int lL = l;
        int rL = r;
        int cost1 = 0 , cost2 = 0;
        bool found1 = 0 , found2 = 0;
        while(lL>=targl){
            extend(lL,rL);
            if(rL>r){found1 = 1;break;}
            if(lL==targl){
                break;
            }
            cost1+=2;
            lL--;
        }
        int lR = l;
        int rR = r;
        while(rR<=targr){
            extend(lR,rR);
            if(lR<l){found2 = 1;break;}
            if(rR==targr){
                break;
            }
            cost2+=2;
            rR++;
        }
        if(found1&&found2){
            all+=min(cost1,cost2);
        }else{
            all+=cost1+cost2;
        }
        l = min({l,lL,lR});
        r = max({r,rL,rR});
    }
    return all;
}
long long minimum_walk(vector<int> p, int s){
    long long ans = 0;
    int n = p.size();
    P.clear();
    for(int i = 0;i<n;i++){
        vis[i] = 0;vis2[i] = 0;
        P.push_back(p[i]);
        ans+=abs(i-p[i]);
    }
    vector<pair<int,int>> lol;
    int rngl = s;
    int rngr = s;
    for(int i = 0;i<n;i++){
        if(!vis[i]){
            mn = 1e9 , mx = -1e9;
            dfs(i);
            DFS(i);
            if(i!=P[i]){
                rngl = min(rngl,mn);
                rngr = max(rngr,mx);
            }
        }
    }
    ans+=get(s,s,rngl,rngr);
    return ans;
}

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