Submission #239133

#	Time	Username	Problem	Language	Result	Execution time	Memory
239133		lyc	Ancient Books (IOI17_books)	C++14	100 / 100	273 ms	26616 KiB

books

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

const int mxN = 1e6+5;
int N, S, E;
int C[mxN], L[mxN], R[mxN], cc;

void ext(int& l, int& r) {
    int x = min(L[C[l]],L[C[r]]), y = max(R[C[l]],R[C[r]]);
    while (true) {
        if (x < l) {
            --l;
            x = min(x,L[C[l]]);
            y = max(y,R[C[l]]);
        } else if (r < y) {
            ++r;
            x = min(x,L[C[r]]);
            y = max(y,R[C[r]]);
        } else break;
    }
}

long long minimum_walk(std::vector<int> p, int s) {
    N = SZ(p);
    long long lb = 0;
    cc = 0;
    S = N-1, E = 0;
    FOR(i,0,N-1){
        lb += abs(p[i]-i);
        if (C[i]) continue;
        C[i] = ++cc;
        L[cc] = R[cc] = i;
        for (int u = p[i]; u != i; u = p[u]) {
            C[u] = cc;
            L[cc] = min(L[cc],u);
            R[cc] = max(R[cc],u);
        }
        if (L[cc] != R[cc]) S = min(S,L[cc]), E = max(E,R[cc]);
    }
    long long add = 0;
    int l = s, r = s;
    ext(l,r);
    while (S < l || r < E) {
        bool op = 0;
        int cl = 0, cr = 0, nl = -1, nr = -1;
        int x = l, y = r;
        while (S < x) { // calc cl
            cl += 2;
            ext(--x,y);
            if (y > r) { op = 1; break; }
        }
        nl = x;
        x = l, y = r;
        while (y < E) { // calc cr
            cr += 2;
            ext(x,++y);
            if (x < l) { op = 1; break; }
        }
        nr = y;
        if (op) {
            add += min(cl,cr);
        } else { // neither covers 
            add += cl + cr;
        }
        l = nl, r = nr;
    }
    //TRACE(lb _ add);
    return lb + add;
}

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