Submission #921322

#	Time	Username	Problem	Language	Result	Execution time	Memory
921322		salmon	Ancient Books (IOI17_books)	C++14	50 / 100	99 ms	24144 KiB

books

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

int parent[1100100];
int v[1100100];
bool done[1100100];
int l[1100100];
int r[1100100];

pair<int,int> expand_range(int l2, int r2, int h){
    int l1 = min(l2,h);
    int r1 = max(r2,h);

    while(l1 != l2 || r1 != r2){
        if(l1 != l2){
            l2--;
            l1 = min(l1,l[parent[l2]]);
            r1 = max(r1,r[parent[l2]]);
        }
        else{
            r2++;
            l1 = min(l1,l[parent[r2]]);
            r1 = max(r1,r[parent[r2]]);
        }
    }

    return {l2,r2};
}

long long minimum_walk(vector<int> p, int s) {
    int l1 = s;
    int r1 = s;
    int l2 = s;
    int r2 = s;
    long long int some = 0;

    int N = p.size();

    for(int i = 0; i < N; i++){
        done[i] = false;
    }

    for(int i = 0; i < N; i++){
        if(done[i]) continue;

        l[i] = i;
        r[i] = i;
        parent[i] = i;
        int j = p[i];
        some += abs(i - j);
        while(j != i){
            int temp = j;
            parent[j] = i;
            done[j] = true;
            r[i] = max(r[i],j);
            j = p[j];
            some += abs(temp - j);
        }
    }

    l2 = l[parent[s]];
    r2 = r[parent[s]];

    while(l1 != l2 || r1 != r2){
        if(l1 != l2){
            l1--;
            l2 = min(l2,l[parent[l1]]);
            r2 = max(r2,r[parent[l1]]);
        }
        else{
            r1++;
            l2 = min(l2,l[parent[r1]]);
            r2 = max(r2,r[parent[r1]]);
        }
    }

    int l3l = l1;
    int r3l = r1;

    int l3r = l1;
    int r3r = r1;

    while(l1 != 0 || r1 != N - 1){
        l3l = l1;
        r3l = r1;

        l3r = l1;
        r3r = r1;

        int tcoft = 0;
        int coft = 0;

        while(!(r1 < r3l && l3r < l1)){
            coft += 2;
            tcoft += 2;

            if(l3l > 0){
                pair<int,int> ii = expand_range(l3l,r3l,l3l - 1);
                l3l = ii.first;
                r3l = ii.second;
                tcoft -= 2;
            }

            if(r3r < N - 1){
                pair<int,int> ii = expand_range(l3r,r3r,r3r+1);
                l3r = ii.first;
                r3r = ii.second;
                tcoft -= 2;
            }

            if(!(r1 < r3l && l3r < l1) && l3l == 0 && r3r == N - 1){
                some += tcoft;
                break;
            }
        }

        some += coft;
        l1 = min(l3l,l1);
        l1 = min(l3r,l1);


        r1 = max(r3l,r1);
        r1 = max(r3r,r1);
    }

    for(int i = N - 1; i > s; i--){
        if(p[i] != i) break;
        some -= 2;
    }

    return some;
}

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