Submission #893211

#	Time	Username	Problem	Language	Result	Execution time	Memory
893211		vjudge1	Ancient Books (IOI17_books)	C++17	50 / 100	98 ms	29520 KiB

books

#include "books.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using ii = pair<int, int>;

struct UF {
    vi e;
    UF(int N) : e(N, -1) {}
    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    int join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return 0;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return 1;
    }
};

long long minimum_walk(vi p, int s) {
    int n = p.size();
    vi on(n, 0);
    vi vma(n, 0), vmi(n, n);
    for(int i = 0; i < n; ++i) {
        if(i) vma[i] = vma[i - 1];
        vma[i] = max(vma[i], p[i]);
    }
    for(int i = n - 1; i >= 0; --i) {
        if(i + 1 < n) vmi[i] = vmi[i + 1];
        vmi[i] = min(vmi[i], p[i]);
    }
    for(int i = 0; i + 1 < n; ++i) {
        if(vma[i] > vmi[i + 1]) {
            on[i] = 1;
        } 
    }
    vi ondr(n, 0);
    for(int i = n - 1; i >= 0; --i) {
        if(i + 1 < n) ondr[i] = ondr[i + 1];
        ondr[i] += on[i];
    }
    ll re = 0;
    for(int i = 0; i < n; ++i) 
        re += abs(i - p[i]);
    for(int i = 0; i < n; ++i) {
        if(!on[i] && ondr[i]) {
            re += 2;
        }
    }
    return re;
}

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