Submission #1199538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199538		Aviansh	Ancient Books (IOI17_books)	C++20	50 / 100	129 ms	37816 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

struct dsu{
    vector<int>root;
    vector<int>siz;
    vector<int>maxima;
    vector<int>minima;
    dsu(int n){
        maxima=vector<int>(n);
        iota(maxima.begin(),maxima.end(),0);
        minima=vector<int>(n);
        iota(minima.begin(),minima.end(),0);
        root=vector<int>(n);
        iota(root.begin(),root.end(),0);
        siz=vector<int>(n,1);
    }
    bool unite(int x, int y){
        x=findRoot(x);
        y=findRoot(y);
        if(x==y)
            return 0;
        if(siz[x]<siz[y]){
            swap(x,y);
        }
        siz[x]+=siz[y];
        root[y]=x;
        maxima[x]=max(maxima[x],maxima[y]);
        return 1;
    }
    int findRoot(int x){
        if(x==root[x])
            return x;
        return root[x]=findRoot(root[x]);
    }
};

long long minimum_walk(vector<int> p, int s) {
    long long ans = 0;
    int n = p.size();
    dsu ds(n);
    vector<int>interesting;
    for(int i = 0;i<n;i++){
        ans+=abs(i-p[i]);
        ds.unite(i,p[i]);
        if(i!=p[i]){
            interesting.push_back(i);
        }
    }
    vector<array<int,2>>rangs(n);
    for(int i = 0;i<n;i++){
        rangs[i][0]=ds.minima[i];
        rangs[i][1]=ds.maxima[i];
    }
    sort(rangs.begin(),rangs.end());
    vector<array<int,2>>merged;
    for(int i = 0;i<n;i++){
        if(rangs[i][0]==rangs[i][1])
            continue;
        if(merged.size()){
            if(rangs[i][0]<merged.back()[1]){
                merged.back()[1]=max(merged.back()[1],rangs[i][1]);
            }
            else{
                merged.push_back(rangs[i]);
            }
        }
        else{
            merged.push_back(rangs[i]);
        }
    }
    if(merged.size()==0){
        return 0;
    }
    int prev = merged[0][1];
    for(int i = 1;i<merged.size();i++){
        ans+=2*(merged[i][0]-prev);
        prev=merged[i][1];
    }
    if(s>=merged[0][0]&&s<=merged[merged.size()-1][1]){
        int ind = upper_bound(merged.begin(),merged.end(),(array<int,2>){s,1000000000})-merged.begin();
        ind--;
        if(ind>=0){
            if(merged[ind][0]<=s&&s<=merged[ind][1]){
                //withing a range, must add something to get into the range.
                int upper = upper_bound(interesting.begin(),interesting.end(),s)-interesting.begin();
                int lower = s-interesting[upper-1];
                upper=interesting[upper]-s;
                ans+=2*min(lower,upper);
            }
        }
        return ans;
    }
    ans+=2*min(abs(merged[0][0]-s),abs(merged[merged.size()-1][1]-s));
    return ans;
}

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