Submission #938141

#	Time	Username	Problem	Language	Result	Execution time	Memory
938141		snpmrnhlol	Ancient Books (IOI17_books)	C++17	100 / 100	120 ms	23920 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6;
const ll inf = 2e9;
bool vis[N];
vector <int> points;
int l[N],r[N];
long long minimum_walk(std::vector<int> p, int s) {
    int n = p.size();
    ll ans = 0;
    ll mn2 = s;
    ll mx2 = s;
    for(ll i = 0;i < n;i++){
        ans+=abs(i - p[i]);
        if(i != p[i]){
            mx2 = max(mx2,i);
            mn2 = min(mn2,i);
        }
        if(!vis[i]){
            points.clear();
            int nr = i;
            int mx = -inf;
            int mn = inf;
            while(!vis[nr]){
                vis[nr] = 1;
                mx = max(mx,nr);
                mn = min(mn,nr);
                points.push_back(nr);
                nr = p[nr];
            }
            for(auto j:points){
                l[j] = mn;
                r[j] = mx;
            }
        }
    }
    int curl,curr,exl,exr;
    curl = s;exl = l[s];
    curr = s;exr = r[s];
    //cout<<mn2<<' '<<mx2<<' '<<exl<<' '<<exr<<' '<<curl<<' '<<curr<<'\n';
    while(exl > mn2 || exr < mx2){
        if(curl > exl){
            curl--;
            exl = min(exl,l[curl]);
            exr = max(exr,r[curl]);
        }else if(curr < exr){
            curr++;
            exl = min(exl,l[curr]);
            exr = max(exr,r[curr]);
        }else{
            //cout<<curl<<' '<<curr<<'\n';
            int costl = 0;
            bool ok = 0;
            int x = exl;
            int exl2 = exl;
            while(x > mn2){
                exl2 = min(exl2,l[x]);
                if(x == exl2){
                    costl+=2;
                    exl2--;
                }
                x--;
                if(r[x] > exr){
                    ok = 1;
                    break;
                }
            }
            int costr = 0;
            int exr2 = exr;
            x = exr;
            while(x < mx2){
                exr2 = max(exr2,r[x]);
                if(x == exr2){
                    costr+=2;
                    exr2++;
                }
                x++;
                if(l[x] < exl){
                    ok = 1;
                    break;
                }
            }
            if(ok){
                if(costl > costr){
                    exr = exr2;
                    ans+=costr;
                }else{
                    exl = exl2;
                    ans+=costl;
                }
            }else{
                ans+=costl;
                ans+=costr;
                break;
            }
        }
    }
	return ans;
}
/**
3 1
2 1 0
**/

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