Submission #1006479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006479		thangdz2k7	Ancient Books (IOI17_books)	C++17	0 / 100	0 ms	348 KiB

books

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int L = -1, R = -1, p[N], n, l, r;

int g(int &l, int &r){
    int ed = r + 1;
    int st = n + 1;
    int be = r;
    int a = 0;
    while (r <= R && r < ed){
        ++ r;
        if (r == R + 1) break;
        a += 2;
        ed = max(ed, p[r]);
        st = min(st, p[r]);
        if (st < be) break;
    }

    be = l;
    ed = l - 1;
    st = -1;
    int b = 0;
    while (l > ed && l >= L){
        -- l;
        if (l == L - 1) return a + b;
        b += 2;
        ed = min(ed, p[l]);
        st = max(st, p[l]);
        if (st > be) break;
    }

    return min(a, b);
}

long long minimum_walk(vector <int> arr, int s){
    int n = arr.size();
    for (int i = 0; i < n; ++ i) p[i] = arr[i];

    long long ans = 0;
    for (int i = 0; i < n; ++ i){
        ans += abs(p[i] - i);
        if (p[i] != i){
            if (L != -1) L = i;
            R = i;
        }
    }

    l = s;
    r = s;

    while (L <= l && r <= R) ans += g(l, r);

    return ans;
}

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