제출 #228098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228098		VEGAnn	Ancient Books (IOI17_books)	C++14	0 / 100	5 ms	384 KiB

books

#include <bits/stdc++.h>
#include "books.h"
//#include "grader.h"
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 1000100;
const ll OO = 1e18;
bool mrk[N];
queue<int> q;
ll ans = 0, cl, cr;
int n, le, ri, mem_l[N], mem_r[N], il[N], ir[N], loc_l, loc_r, S, P[N];

void extend(){
    while (sz(q)){
        int v = q.front(); q.pop();

        int nl = v, nr = P[v];

        if (nl > nr) swap(nl, nr);

        if (nl < le){
            for (int j = nl; j < le; j++)
                q.push(j);
            le = nl;
        }

        if (nr > ri){
            for (int j = ri + 1; j <= nr; j++)
                q.push(j);
            ri = nr;
        }
    }
}

void get_lf(){
    int lst = le;
    loc_l = -1;
    cl = 0;

    for (int i = le - 1; i >= 0; i--){
        if (i < lst) cl += 2;

        if (mem_l[i] >= 0)
            lst = min(lst, mem_l[i]);

        if (ir[i] > S){
            loc_l = i;
            return;
        }
    }
}

void get_rt(){
    int lst = ri;
    loc_r = -1;
    cr = 0;

    for (int i = ri + 1; i < n; i++){
        if (i > lst) cr += 2;

        if (mem_r[i] >= 0)
            lst = max(lst, mem_r[i]);

        if (il[i] < S){
            loc_r = i;
            return;
        }
    }
}

long long minimum_walk(std::vector<int> p, int s) {
    n = sz(p);
    S = s;

    bool was = 0;

    fill(mem_l, mem_l + n, -1);
    fill(mem_r, mem_r + n, -1);

    for (int i = 0; i < n; i++){
        P[i] = p[i];
        ans += abs(p[i] - i);

        if (p[i] != i) {
            was = 1;
            int lf = i;
            int rt = p[i];

            if (lf > rt) swap(lf, rt);

            mem_l[rt] = lf;
            mem_r[lf] = rt;
        }

        if (mrk[i]) continue;

        int cr = i, mn = i, mx = i;

        while (!mrk[cr]){
            mn = min(mn, cr);
            mx = max(mx, cr);
            mrk[cr] = 1;
            cr = p[cr];
        }

        il[i] = mn;
        ir[i] = mx;

        cr = p[i];

        while (cr != i){
            il[cr] = mn;
            ir[cr] = mx;
            cr = p[cr];
        }
    }

    if (!was) return 0;

    le = ri = s;

    q.push(s);

    extend();

    while (1){
        get_lf();
        get_rt();

        if (loc_l < 0) {
            ans += cl + cr;
            break;
        }

        ans += min(cl, cr);

        for (int j = loc_l; j < le; j++)
            q.push(j);
        le = loc_l;

        extend();
    }

	return ans;
}

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